oj.uz

Submission #598995

# Submission time Handle Problem Language Result Execution time Memory
598995 2022-07-19T08:46:14 Z pakhomovee Wombats (IOI13_wombats) C++17
39 / 100
 20000 ms 24040 KB 
#include "wombats.h"
#include <algorithm>
#include <vector>
#include <queue>
#include <cassert>
#include <cstring>

using namespace std;

int n, m;
int h[5000][200];
int v[5000][200];

int calc[200][200];
int dist[5000 * 200];
bool used[5000 * 200];
const int inf = 2e9;

void djkstra(int s, int* arr) {
    priority_queue<pair<int, int>> q;
    fill(dist, dist + n * m, inf);
    fill(used, used + n * m, false);
    dist[s] = 0;
    q.push({ -dist[s], s });
    while (!q.empty()) {
        int u = q.top().second;
        q.pop();
        if (used[u]) continue;
        used[u] = true;
        int r = u / m;
        int c = u % m;
        if (r + 1 < n && dist[u + m] > dist[u] + v[r][c]) {
            dist[u + m] = dist[u] + v[r][c];
            q.push({ -dist[u + m], u + m });
        }
        if (c > 0 && dist[u - 1] > dist[u] + h[r][c - 1]) {
            dist[u - 1] = dist[u] + h[r][c - 1];
            q.push({ -dist[u - 1], u - 1 });
        }
        if (c + 1 < m && dist[u + 1] > dist[u] + h[r][c]) {
            dist[u + 1] = dist[u] + h[r][c];
            q.push({ -dist[u + 1], u + 1 });
        }
    }
    for (int i = (n - 1) * m; i < n * m; ++i) {
        arr[i - (n - 1) * m] = dist[i];
    }
}

void recalc() {
    for (int i = 0; i < m; ++i) {
        djkstra(i, calc[i]);
    }
}

void init(int R, int C, int H[5000][200], int V[5000][200]) {
    n = R;
    m = C;
    for (int i = 0; i < 5000; ++i) {
        memcpy(h[i], H[i], 200 * sizeof(int));
    }
    for (int i = 0; i < 5000; ++i) {
        memcpy(v[i], V[i], 200 * sizeof(int));
    }
    recalc();
}

void changeH(int P, int Q, int W) {
    h[P][Q] = W;
    recalc();
}

void changeV(int P, int Q, int W) {
    v[P][Q] = W;
    recalc();
}

int escape(int V1, int V2) {
    return calc[V1][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
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 12080 KB Output is correct
2 Correct 68 ms 12088 KB Output is correct
3 Correct 131 ms 14808 KB Output is correct
4 Correct 75 ms 12192 KB Output is correct
5 Correct 69 ms 12084 KB Output is correct
6 Correct 5 ms 8148 KB Output is correct
7 Correct 6 ms 8104 KB Output is correct
8 Correct 6 ms 8148 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8136 KB Output is correct
2 Correct 6 ms 8148 KB Output is correct
3 Correct 5 ms 8148 KB Output is correct
4 Correct 6 ms 8148 KB Output is correct
5 Correct 6 ms 8148 KB Output is correct
6 Correct 8 ms 8148 KB Output is correct
7 Correct 7 ms 8104 KB Output is correct
8 Correct 6 ms 8148 KB Output is correct
9 Correct 7 ms 8204 KB Output is correct
10 Correct 6 ms 8108 KB Output is correct
11 Correct 75 ms 9244 KB Output is correct
12 Correct 7 ms 8192 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 11277 ms 8508 KB Output is correct
2 Correct 17855 ms 8640 KB Output is correct
3 Correct 11283 ms 8576 KB Output is correct
4 Correct 11236 ms 8508 KB Output is correct
5 Correct 11562 ms 8500 KB Output is correct
6 Correct 7 ms 8148 KB Output is correct
7 Correct 7 ms 8104 KB Output is correct
8 Correct 7 ms 8148 KB Output is correct
9 Execution timed out 20060 ms 8516 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 428 ms 16064 KB Output is correct
2 Correct 907 ms 16052 KB Output is correct
3 Correct 412 ms 16172 KB Output is correct
4 Correct 462 ms 17444 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 11115 ms 8504 KB Output is correct
2 Correct 17675 ms 8672 KB Output is correct
3 Correct 11329 ms 8504 KB Output is correct
4 Correct 11307 ms 8516 KB Output is correct
5 Correct 11119 ms 8504 KB Output is correct
6 Correct 403 ms 16060 KB Output is correct
7 Correct 909 ms 16052 KB Output is correct
8 Correct 391 ms 16060 KB Output is correct
9 Correct 436 ms 17328 KB Output is correct
10 Correct 66 ms 11988 KB Output is correct
11 Correct 69 ms 12092 KB Output is correct
12 Correct 133 ms 14864 KB Output is correct
13 Correct 68 ms 12088 KB Output is correct
14 Correct 74 ms 12092 KB Output is correct
15 Correct 5 ms 8148 KB Output is correct
16 Correct 6 ms 8148 KB Output is correct
17 Correct 6 ms 8148 KB Output is correct
18 Correct 6 ms 8176 KB Output is correct
19 Correct 6 ms 8148 KB Output is correct
20 Correct 6 ms 8148 KB Output is correct
21 Correct 6 ms 8148 KB Output is correct
22 Correct 6 ms 8188 KB Output is correct
23 Correct 7 ms 8204 KB Output is correct
24 Correct 6 ms 8148 KB Output is correct
25 Correct 69 ms 10444 KB Output is correct
26 Correct 7 ms 8148 KB Output is correct
27 Execution timed out 20095 ms 8496 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 11152 ms 8504 KB Output is correct
2 Correct 17855 ms 8600 KB Output is correct
3 Correct 13576 ms 8504 KB Output is correct
4 Correct 13889 ms 8504 KB Output is correct
5 Correct 13058 ms 8500 KB Output is correct
6 Correct 484 ms 16060 KB Output is correct
7 Correct 1189 ms 16052 KB Output is correct
8 Correct 504 ms 16060 KB Output is correct
9 Correct 508 ms 17356 KB Output is correct
10 Correct 71 ms 12076 KB Output is correct
11 Correct 70 ms 11988 KB Output is correct
12 Correct 135 ms 14820 KB Output is correct
13 Correct 74 ms 12088 KB Output is correct
14 Correct 75 ms 12084 KB Output is correct
15 Execution timed out 20090 ms 24040 KB Time limit exceeded
16 Halted 0 ms 0 KB -