oj.uz

Submission #108574

# Submission time Handle Problem Language Result Execution time Memory
108574 2019-04-30T09:10:32 Z tictaccat Wombats (IOI13_wombats) C++11
21 / 100
 674 ms 17500 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)); 
vector<vector<int>> ans(210,vector<int>(210,-1));

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;
    ans.clear();
}

void changeV(int P, int Q, int W) {
    /* ... */
    V[P][Q] = W;
    ans.clear();
    ans.assign(210,vector<int>(210,-1));
}

int escape(int V1, int V2) {
   // assert(V1 == 0 && V2 == 0);

    if (ans[V1][V2] != -1) {
        //cout << "test\n";
        return ans[V1][V2];
    }

    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 (ans[V1][V2] = 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
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 13480 KB Output is correct
2 Correct 205 ms 13368 KB Output is correct
3 Correct 307 ms 15032 KB Output is correct
4 Correct 238 ms 13476 KB Output is correct
5 Correct 241 ms 13400 KB Output is correct
6 Correct 15 ms 9216 KB Output is correct
7 Correct 16 ms 9088 KB Output is correct
8 Correct 14 ms 9088 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 9216 KB Output is correct
2 Correct 16 ms 9216 KB Output is correct
3 Correct 14 ms 9216 KB Output is correct
4 Correct 44 ms 9216 KB Output is correct
5 Correct 24 ms 9216 KB Output is correct
6 Correct 35 ms 9208 KB Output is correct
7 Correct 38 ms 9216 KB Output is correct
8 Correct 39 ms 9208 KB Output is correct
9 Correct 38 ms 9216 KB Output is correct
10 Correct 40 ms 9216 KB Output is correct
11 Correct 102 ms 10360 KB Output is correct
12 Correct 38 ms 9216 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 9344 KB Output is correct
2 Correct 298 ms 9644 KB Output is correct
3 Incorrect 87 ms 9336 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 674 ms 17500 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 9432 KB Output is correct
2 Correct 280 ms 9680 KB Output is correct
3 Incorrect 88 ms 9344 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 9400 KB Output is correct
2 Correct 273 ms 9600 KB Output is correct
3 Incorrect 97 ms 9464 KB Output isn't correct
4 Halted 0 ms 0 KB -