oj.uz

Submission #1068958

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

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

const int N = 5005, K = 105;
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 47 ms 23128 KB Output is correct
2 Correct 47 ms 23128 KB Output is correct
3 Correct 87 ms 25936 KB Output is correct
4 Correct 48 ms 23128 KB Output is correct
5 Correct 47 ms 23132 KB Output is correct
6 Correct 3 ms 16728 KB Output is correct
7 Correct 3 ms 16732 KB Output is correct
8 Correct 3 ms 16732 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16868 KB Output is correct
2 Correct 3 ms 16840 KB Output is correct
3 Correct 2 ms 16732 KB Output is correct
4 Correct 4 ms 20828 KB Output is correct
5 Correct 3 ms 20956 KB Output is correct
6 Correct 5 ms 20828 KB Output is correct
7 Correct 4 ms 20828 KB Output is correct
8 Correct 3 ms 20828 KB Output is correct
9 Correct 4 ms 20828 KB Output is correct
10 Correct 4 ms 21012 KB Output is correct
11 Correct 46 ms 23132 KB Output is correct
12 Correct 4 ms 20828 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 21584 KB Output is correct
2 Correct 166 ms 21668 KB Output is correct
3 Correct 115 ms 21596 KB Output is correct
4 Correct 116 ms 21592 KB Output is correct
5 Correct 116 ms 21472 KB Output is correct
6 Correct 3 ms 16728 KB Output is correct
7 Correct 3 ms 16864 KB Output is correct
8 Correct 3 ms 16732 KB Output is correct
9 Correct 79 ms 21596 KB Output is correct
10 Correct 3 ms 20828 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 26972 KB Output is correct
2 Correct 738 ms 26968 KB Output is correct
3 Correct 338 ms 26972 KB Output is correct
4 Correct 355 ms 28368 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 21572 KB Output is correct
2 Correct 183 ms 21664 KB Output is correct
3 Correct 122 ms 21596 KB Output is correct
4 Correct 127 ms 21596 KB Output is correct
5 Correct 126 ms 21476 KB Output is correct
6 Correct 336 ms 27136 KB Output is correct
7 Correct 800 ms 27128 KB Output is correct
8 Correct 306 ms 26972 KB Output is correct
9 Correct 357 ms 28420 KB Output is correct
10 Correct 56 ms 22616 KB Output is correct
11 Correct 52 ms 22620 KB Output is correct
12 Correct 101 ms 25424 KB Output is correct
13 Correct 56 ms 22832 KB Output is correct
14 Correct 52 ms 22620 KB Output is correct
15 Correct 3 ms 16856 KB Output is correct
16 Correct 3 ms 16828 KB Output is correct
17 Correct 3 ms 16732 KB Output is correct
18 Correct 4 ms 20828 KB Output is correct
19 Correct 5 ms 18776 KB Output is correct
20 Correct 3 ms 16984 KB Output is correct
21 Correct 6 ms 21084 KB Output is correct
22 Correct 5 ms 21008 KB Output is correct
23 Correct 5 ms 20828 KB Output is correct
24 Correct 5 ms 20828 KB Output is correct
25 Correct 71 ms 23124 KB Output is correct
26 Correct 5 ms 20828 KB Output is correct
27 Correct 93 ms 21480 KB Output is correct
28 Runtime error 162 ms 104068 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 90 ms 21592 KB Output is correct
2 Correct 190 ms 21592 KB Output is correct
3 Correct 142 ms 21596 KB Output is correct
4 Correct 123 ms 21596 KB Output is correct
5 Correct 126 ms 21592 KB Output is correct
6 Correct 320 ms 26968 KB Output is correct
7 Correct 760 ms 26968 KB Output is correct
8 Correct 321 ms 27132 KB Output is correct
9 Correct 397 ms 28500 KB Output is correct
10 Correct 52 ms 23340 KB Output is correct
11 Correct 46 ms 23128 KB Output is correct
12 Correct 134 ms 25728 KB Output is correct
13 Correct 49 ms 23132 KB Output is correct
14 Correct 51 ms 23128 KB Output is correct
15 Runtime error 233 ms 101608 KB Execution killed with signal 6
16 Halted 0 ms 0 KB -