oj.uz

Submission #1076200

# Submission time Handle Problem Language Result Execution time Memory
1076200 2024-08-26T11:43:35 Z shmax Wombats (IOI13_wombats) C++17
55 / 100
 20000 ms 262144 KB 
#include "wombats.h"
#include <bits/stdc++.h>

using namespace std;

template<typename T>
using vec = vector<T>;
vec<vec<pair<int, int>>> g;
vec<vec<int>> dists;

void dijkstra(int start, vec<int> &dist) {
    dist.clear();
    dist.resize(g.size());
    fill(dist.begin(), dist.end(), 1e9);
    dist[start] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    pq.push({0, start});
    while (!pq.empty()) {
        auto [d, v] = pq.top();
        pq.pop();
        if (d > dist[v]) continue;
        for (auto [u, w]: g[v]) {
            if (dist[u] > dist[v] + w) {
                dist[u] = dist[v] + w;
                pq.push({dist[u], u});
            }
        }
    }
}

int r, c;

void calc() {
    for (int i = 0; i < c; i++) {
        dijkstra(i, dists[i]);
    }
}


void init(int R, int C, int H[5000][200], int V[5000][200]) {
    r = R;
    c = C;
    g.resize(R * C);
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (i != R - 1) {
                g[i * C + j].emplace_back(i * C + j + C, V[i][j]);
            }
            if (j != 0) {
                g[i * C + j].emplace_back(i * C + j - 1, H[i][j - 1]);
            }
            if (j != C - 1) {
                g[i * C + j].emplace_back(i * C + j + 1, H[i][j]);
            }
        }
    }
    dists.resize(C);
    calc();
}

void changeH(int x, int y, int val) {
    for (int i = 0; i < g[x * c + y].size(); i++) {
        if (g[x * c + y][i].first == x * c + y + 1) {
            g[x * c + y][i].second = val;
            break;
        }
    }
    for (int i = 0; i < g[x * c + y + 1].size(); i++) {
        if (g[x * c + y + 1][i].first == x * c + y) {
            g[x * c + y + 1][i].second = val;
            break;
        }
    }
    if (c <= 2)
        calc();
}

void changeV(int x, int y, int val) {
    for (int i = 0; i < g[x * c + y].size(); i++) {
        if (g[x * c + y][i].first == x * c + y + c) {
            g[x * c + y][i].second = val;
            break;
        }
    }

    if (c <= 2)
        calc();
}

int escape(int y1, int y2) {
    if (c > 2)
        dijkstra(y1, dists[y1]);
    return dists[y1][r * c - c + y2];
}

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;
      |      ^~~
wombats.cpp: In function 'void changeH(int, int, int)':
wombats.cpp:62:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for (int i = 0; i < g[x * c + y].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~~~~~~
wombats.cpp:68:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for (int i = 0; i < g[x * c + y + 1].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~
wombats.cpp: In function 'void changeV(int, int, int)':
wombats.cpp:79:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for (int i = 0; i < g[x * c + y].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 4456 KB Output is correct
2 Correct 48 ms 4440 KB Output is correct
3 Correct 79 ms 7204 KB Output is correct
4 Correct 41 ms 4444 KB Output is correct
5 Correct 41 ms 4552 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 10 ms 2576 KB Output is correct
5 Correct 5 ms 2396 KB Output is correct
6 Correct 4 ms 2396 KB Output is correct
7 Correct 10 ms 2396 KB Output is correct
8 Correct 9 ms 2392 KB Output is correct
9 Correct 11 ms 2396 KB Output is correct
10 Correct 10 ms 2572 KB Output is correct
11 Correct 5002 ms 4844 KB Output is correct
12 Correct 11 ms 2396 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 7064 KB Output is correct
2 Correct 324 ms 6996 KB Output is correct
3 Correct 214 ms 7136 KB Output is correct
4 Correct 202 ms 7172 KB Output is correct
5 Correct 216 ms 6996 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 312 ms 7136 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 8952 KB Output is correct
2 Correct 718 ms 8792 KB Output is correct
3 Correct 247 ms 8792 KB Output is correct
4 Correct 263 ms 10324 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 6992 KB Output is correct
2 Correct 314 ms 7184 KB Output is correct
3 Correct 199 ms 7252 KB Output is correct
4 Correct 198 ms 7048 KB Output is correct
5 Correct 205 ms 7016 KB Output is correct
6 Correct 241 ms 8956 KB Output is correct
7 Correct 653 ms 8948 KB Output is correct
8 Correct 244 ms 8792 KB Output is correct
9 Correct 273 ms 10204 KB Output is correct
10 Correct 40 ms 4952 KB Output is correct
11 Correct 40 ms 4952 KB Output is correct
12 Correct 88 ms 7660 KB Output is correct
13 Correct 42 ms 5200 KB Output is correct
14 Correct 40 ms 4952 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 10 ms 2576 KB Output is correct
19 Correct 4 ms 2572 KB Output is correct
20 Correct 4 ms 2396 KB Output is correct
21 Correct 9 ms 2396 KB Output is correct
22 Correct 10 ms 2568 KB Output is correct
23 Correct 11 ms 2572 KB Output is correct
24 Correct 10 ms 2396 KB Output is correct
25 Correct 4834 ms 4732 KB Output is correct
26 Correct 11 ms 2392 KB Output is correct
27 Correct 291 ms 7072 KB Output is correct
28 Execution timed out 20056 ms 242776 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 7064 KB Output is correct
2 Correct 317 ms 6992 KB Output is correct
3 Correct 202 ms 7036 KB Output is correct
4 Correct 202 ms 7248 KB Output is correct
5 Correct 198 ms 6996 KB Output is correct
6 Correct 239 ms 8952 KB Output is correct
7 Correct 663 ms 8944 KB Output is correct
8 Correct 272 ms 8792 KB Output is correct
9 Correct 264 ms 10320 KB Output is correct
10 Correct 41 ms 4444 KB Output is correct
11 Correct 40 ms 4956 KB Output is correct
12 Correct 78 ms 7396 KB Output is correct
13 Correct 40 ms 4444 KB Output is correct
14 Correct 40 ms 4440 KB Output is correct
15 Runtime error 3753 ms 262144 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -