oj.uz

Submission #1068961

# Submission time Handle Problem Language Result Execution time Memory
1068961 2024-08-21T13:48:36 Z blackslex Wombats (IOI13_wombats) C++17
55 / 100
 732 ms 184656 KB 
#include "wombats.h"
#include<bits/stdc++.h>

using namespace std;
using pii = pair<int, int>;

const int N = 5005, K = 205;
int n, m, ch[N][K], cv[N][K], d[N][K];
vector<pii> v[N * K];
bool f[K];

int get (int x, int y) {
    return x * m + y;
}

void init(int R, int C, int H[5000][200], int V[5000][200]) {
    n = R; m = C;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m - 1; j++) {
            ch[i][j] = H[i][j];
            v[get(i, j)].emplace_back(get(i, j + 1), H[i][j]);
            v[get(i, j + 1)].emplace_back(get(i, j), H[i][j]);
        }
    }
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < m; j++) {
            cv[i][j] = V[i][j];
            v[get(i, j)].emplace_back(get(i + 1, j), V[i][j]);
        }
    }
    for (int i = 0; i < m; i++) f[i] = 1;
}

void changeH(int P, int Q, int W) {
    int st = get(P, Q), ed = get(P, Q + 1);
    v[st].erase(find(v[st].begin(), v[st].end(), pii(ed, ch[P][Q])));
    v[ed].erase(find(v[ed].begin(), v[ed].end(), pii(st, ch[P][Q])));
    ch[P][Q] = W;
    v[st].emplace_back(ed, W);
    v[ed].emplace_back(st, W);
    for (int i = 0; i < m; i++) f[i] = 1;
}

void changeV(int P, int Q, int W) {
    int st = get(P, Q), ed = get(P + 1, Q);
    v[st].erase(find(v[st].begin(), v[st].end(), pii(ed, cv[P][Q])));
    cv[P][Q] = W;
    v[st].emplace_back(ed, W);
    for (int i = 0; i < m; i++) f[i] = 1;
}

int escape(int V1, int V2) {
    int st = get(0, V1), ed = get(n - 1, V2);
    if (f[V1]) {
        for (int i = 0; i < n * m; i++) d[i][V1] = 1e9;
        priority_queue<pii, vector<pii>, greater<pii>> pq;
        pq.emplace(d[st][V1] = 0, st);
        while (!pq.empty()) {
            auto [nd, nn] = pq.top(); pq.pop();
            for (auto &[tn, td]: v[nn]) {
                if (d[tn][V1] > d[nn][V1] + td) pq.emplace(d[tn][V1] = d[nn][V1] + td, tn);
            }
        }
        f[V1] = 0;
    }
    return d[ed][V1];
}

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 53 ms 39516 KB Output is correct
2 Correct 57 ms 39516 KB Output is correct
3 Correct 98 ms 41300 KB Output is correct
4 Correct 52 ms 39736 KB Output is correct
5 Correct 52 ms 39512 KB Output is correct
6 Correct 7 ms 29020 KB Output is correct
7 Correct 5 ms 29020 KB Output is correct
8 Correct 4 ms 29020 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 29020 KB Output is correct
2 Correct 4 ms 29020 KB Output is correct
3 Correct 5 ms 29020 KB Output is correct
4 Correct 6 ms 33116 KB Output is correct
5 Correct 5 ms 33116 KB Output is correct
6 Correct 5 ms 33112 KB Output is correct
7 Correct 6 ms 33116 KB Output is correct
8 Correct 5 ms 33116 KB Output is correct
9 Correct 6 ms 33116 KB Output is correct
10 Correct 5 ms 33116 KB Output is correct
11 Correct 45 ms 34196 KB Output is correct
12 Correct 6 ms 33116 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 37976 KB Output is correct
2 Correct 169 ms 37976 KB Output is correct
3 Correct 116 ms 37720 KB Output is correct
4 Correct 117 ms 37848 KB Output is correct
5 Correct 118 ms 37972 KB Output is correct
6 Correct 4 ms 29020 KB Output is correct
7 Correct 4 ms 29156 KB Output is correct
8 Correct 5 ms 29020 KB Output is correct
9 Correct 82 ms 37724 KB Output is correct
10 Correct 5 ms 33116 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 316 ms 44636 KB Output is correct
2 Correct 732 ms 44632 KB Output is correct
3 Correct 318 ms 44880 KB Output is correct
4 Correct 332 ms 45304 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 37724 KB Output is correct
2 Correct 167 ms 37980 KB Output is correct
3 Correct 118 ms 37724 KB Output is correct
4 Correct 120 ms 37720 KB Output is correct
5 Correct 117 ms 37720 KB Output is correct
6 Correct 312 ms 44636 KB Output is correct
7 Correct 722 ms 44704 KB Output is correct
8 Correct 322 ms 44632 KB Output is correct
9 Correct 343 ms 45248 KB Output is correct
10 Correct 52 ms 39512 KB Output is correct
11 Correct 53 ms 39740 KB Output is correct
12 Correct 88 ms 41268 KB Output is correct
13 Correct 51 ms 39516 KB Output is correct
14 Correct 53 ms 39736 KB Output is correct
15 Correct 5 ms 29020 KB Output is correct
16 Correct 4 ms 29020 KB Output is correct
17 Correct 5 ms 29020 KB Output is correct
18 Correct 6 ms 33116 KB Output is correct
19 Correct 5 ms 33112 KB Output is correct
20 Correct 6 ms 33364 KB Output is correct
21 Correct 6 ms 33324 KB Output is correct
22 Correct 5 ms 33116 KB Output is correct
23 Correct 5 ms 33116 KB Output is correct
24 Correct 6 ms 33228 KB Output is correct
25 Correct 45 ms 34132 KB Output is correct
26 Correct 6 ms 33116 KB Output is correct
27 Correct 80 ms 37752 KB Output is correct
28 Runtime error 153 ms 137200 KB Execution killed with signal 11
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 37724 KB Output is correct
2 Correct 173 ms 37976 KB Output is correct
3 Correct 117 ms 37932 KB Output is correct
4 Correct 117 ms 37724 KB Output is correct
5 Correct 116 ms 37912 KB Output is correct
6 Correct 313 ms 44632 KB Output is correct
7 Correct 728 ms 44880 KB Output is correct
8 Correct 312 ms 44636 KB Output is correct
9 Correct 361 ms 45368 KB Output is correct
10 Correct 52 ms 39512 KB Output is correct
11 Correct 51 ms 39516 KB Output is correct
12 Correct 90 ms 41296 KB Output is correct
13 Correct 52 ms 39516 KB Output is correct
14 Correct 51 ms 39732 KB Output is correct
15 Runtime error 282 ms 184656 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -