oj.uz

Submission #108572

# Submission time Handle Problem Language Result Execution time Memory
108572 2019-04-30T09:07:18 Z tictaccat Wombats (IOI13_wombats) C++14
28 / 100
 20000 ms 17796 KB 
#include "wombats.h"
#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9;

int sum, R, C;
vector<vector<int>> H(5050,vector<int>(210,INF)), V(5050,vector<int>(210,INF)); 

void init(int Rt, int Ct, int tH[5000][200], int tV[5000][200]) {
    /* ... */
    R = Rt; C = Ct;
    for (int i = 0; i < 5000; i++) for (int j = 0; j < 200; j++) {H[i][j] = tH[i][j]; V[i][j] = tV[i][j];}
}

void changeH(int P, int Q, int W) {
    /* ... */
    H[P][Q] = W;
}

void changeV(int P, int Q, int W) {
    /* ... */
    V[P][Q] = W;
}

int escape(int V1, int V2) {
   // assert(V1 == 0 && V2 == 0);
    priority_queue<tuple<int,int,int>> pq;
    vector<vector<int>> dist(R,vector<int>(C,-1));

    pq.push(make_tuple(0,V1,0));

    while (!pq.empty()) {
        int c,r,d; tie(d,c,r) = pq.top(); pq.pop();
        if (dist[r][c] != -1) continue;
        d *= -1;
        dist[r][c] = d;
        if (c > 0 && (dist[r][c-1] == -1 || dist[r][c-1] > d + H[r][c-1])) pq.push(make_tuple(-(d + H[r][c-1]),c-1,r));
        if (c < C-1 && (dist[r][c+1] == -1 || dist[r][c+1] > d + H[r][c])) pq.push(make_tuple(-(d + H[r][c]),c+1,r));
        if (r < R-1 && (dist[r+1][c] == -1 || dist[r+1][c] > d + V[r][c])) pq.push(make_tuple(-(d + V[r][c]),c,r+1));
    }

    return dist[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]
  int res;
      ^~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 13300 KB Output is correct
2 Correct 222 ms 13188 KB Output is correct
3 Execution timed out 20078 ms 13896 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 8960 KB Output is correct
2 Correct 15 ms 8960 KB Output is correct
3 Correct 15 ms 8960 KB Output is correct
4 Correct 43 ms 9088 KB Output is correct
5 Correct 26 ms 9080 KB Output is correct
6 Correct 37 ms 9088 KB Output is correct
7 Correct 40 ms 9080 KB Output is correct
8 Correct 36 ms 9088 KB Output is correct
9 Correct 46 ms 9080 KB Output is correct
10 Correct 44 ms 9088 KB Output is correct
11 Correct 11928 ms 10288 KB Output is correct
12 Correct 45 ms 8960 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 9248 KB Output is correct
2 Correct 323 ms 9436 KB Output is correct
3 Correct 221 ms 9336 KB Output is correct
4 Correct 205 ms 9216 KB Output is correct
5 Correct 204 ms 9188 KB Output is correct
6 Correct 15 ms 8960 KB Output is correct
7 Correct 15 ms 8960 KB Output is correct
8 Correct 14 ms 8960 KB Output is correct
9 Correct 239 ms 9216 KB Output is correct
10 Correct 16 ms 8960 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1143 ms 17092 KB Output is correct
2 Correct 2041 ms 17432 KB Output is correct
3 Correct 1113 ms 17292 KB Output is correct
4 Execution timed out 20096 ms 17708 KB Time limit exceeded

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 9336 KB Output is correct
2 Correct 230 ms 9444 KB Output is correct
3 Correct 218 ms 9216 KB Output is correct
4 Correct 244 ms 9216 KB Output is correct
5 Correct 227 ms 9216 KB Output is correct
6 Correct 1104 ms 17400 KB Output is correct
7 Correct 2640 ms 17412 KB Output is correct
8 Correct 1210 ms 17280 KB Output is correct
9 Execution timed out 20067 ms 17732 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 9208 KB Output is correct
2 Correct 261 ms 9412 KB Output is correct
3 Correct 260 ms 9336 KB Output is correct
4 Correct 204 ms 9216 KB Output is correct
5 Correct 206 ms 9396 KB Output is correct
6 Correct 1079 ms 17144 KB Output is correct
7 Correct 2260 ms 17480 KB Output is correct
8 Correct 1033 ms 17348 KB Output is correct
9 Execution timed out 20037 ms 17796 KB Time limit exceeded
10 Halted 0 ms 0 KB -