oj.uz

Submission #935071

# Submission time Handle Problem Language Result Execution time Memory
935071 2024-02-28T14:27:52 Z anton Wombats (IOI13_wombats) C++17
28 / 100
 20000 ms 24912 KB 
#include "wombats.h"
#include<bits/stdc++.h>

using namespace std;
#define pii pair<int, int>

int tr[5000][200][3];
int delta[3][2] = {{0, 1}, {0, -1}, {1, 0}};
int dist[5000][200];

int r, c;
void init(int R, int C, int H[5000][200], int V[5000][200]) {
    r= R;
    c= C;
    for(int p = 0; p<R; p++){
        for(int q=  0; q<C-1; q++){
            tr[p][q][0] = H[p][q];
            tr[p][q+1][1] = H[p][q];
        }
        for(int q=  0; q<C; q++){
            tr[p][q][2] = V[p][q];
        }
    }

}

void changeH(int P, int Q, int W) {
    tr[P][Q][0] = W;
    tr[P][Q+1][1] = W;
}

void changeV(int P, int Q, int W) {
    tr[P][Q][2] = W;
}

vector<pair<pii, int>> gen_adj(pii pos){
    vector<pair<pii, int>> res;
    for(int trid = 0; trid<3; trid++){
        pii potential = {pos.first + delta[trid][0], pos.second + delta[trid][1]};
        if(potential.first<r && potential.second>=0 && potential.second<c){
            res.push_back({potential, tr[pos.first][pos.second][trid]});
        }
    }
    return res;
}

int dijkstra(pii begin, pii dest){

    for(int i = 0; i<r; i++){
        for(int j = 0; j<c; j++){
            dist[i][j]  = 1e9;
        }
    }
    priority_queue<pair<int, pii>> pq;
    pq.push({0, begin});
    dist[begin.first][begin.second] = 0;

    while(pq.size()>0){
        auto cur = pq.top();
        pq.pop();


        pii pos=  cur.second;
        int d = -cur.first;
        //cout<<pos.first<<" "<<pos.second<<" "<<d<<endl;
        if(d== dist[pos.first][pos.second]){
            auto adj = gen_adj(pos);
            for(auto e: adj){
                if(d + e.second< dist[e.first.first][e.first.second]){
                    dist[e.first.first][e.first.second]= d + e.second;
                    pq.push({-d-e.second, e.first});
                }
            }
        }
    }
    return dist[dest.first][dest.second];
}

int escape(int V1, int V2) {
    return dijkstra(pii(0, V1), pii(r-1, V2));
}

Compilation message

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   15 |  int res;
      |      ^~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 21864 KB Output is correct
2 Correct 95 ms 21876 KB Output is correct
3 Execution timed out 20015 ms 23804 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 1 ms 4696 KB Output is correct
4 Correct 29 ms 6488 KB Output is correct
5 Correct 16 ms 6492 KB Output is correct
6 Correct 21 ms 6492 KB Output is correct
7 Correct 27 ms 6748 KB Output is correct
8 Correct 20 ms 6492 KB Output is correct
9 Correct 28 ms 6492 KB Output is correct
10 Correct 22 ms 6492 KB Output is correct
11 Correct 11159 ms 8956 KB Output is correct
12 Correct 27 ms 6488 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 6748 KB Output is correct
2 Correct 236 ms 6880 KB Output is correct
3 Correct 177 ms 6992 KB Output is correct
4 Correct 174 ms 6744 KB Output is correct
5 Correct 173 ms 6744 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 244 ms 6780 KB Output is correct
10 Correct 1 ms 6488 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 770 ms 24232 KB Output is correct
2 Correct 1402 ms 23972 KB Output is correct
3 Correct 776 ms 23976 KB Output is correct
4 Execution timed out 20056 ms 24420 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 6996 KB Output is correct
2 Correct 238 ms 6896 KB Output is correct
3 Correct 175 ms 6744 KB Output is correct
4 Correct 177 ms 6844 KB Output is correct
5 Correct 170 ms 6744 KB Output is correct
6 Correct 751 ms 23976 KB Output is correct
7 Correct 1390 ms 24144 KB Output is correct
8 Correct 755 ms 23900 KB Output is correct
9 Execution timed out 20031 ms 24912 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 6748 KB Output is correct
2 Correct 237 ms 6900 KB Output is correct
3 Correct 174 ms 6748 KB Output is correct
4 Correct 170 ms 6752 KB Output is correct
5 Correct 172 ms 6748 KB Output is correct
6 Correct 767 ms 23984 KB Output is correct
7 Correct 1398 ms 23964 KB Output is correct
8 Correct 754 ms 23972 KB Output is correct
9 Execution timed out 20003 ms 24664 KB Time limit exceeded
10 Halted 0 ms 0 KB -