oj.uz

Submission #490889

# Submission time Handle Problem Language Result Execution time Memory
490889 2021-11-29T16:03:35 Z dxz05 Wombats (IOI13_wombats) C++14
28 / 100
 20000 ms 33328 KB 
#include "wombats.h"
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e6 + 3e2;

vector<pair<int, int>> g[MAXN];

#define MP make_pair

int N, M;

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++){
            g[i * M + j].emplace_back(i * M + j + 1, H[i][j]);
            g[i * M + j + 1].emplace_back(i * M + j, H[i][j]);
        }
    }

    for (int i = 0; i < N - 1; i++){
        for (int j = 0; j < M; j++){
            g[i * M + j].emplace_back((i + 1) * M + j, V[i][j]);
        }
    }

}

void changeH(int P, int Q, int W) {
    int x = P * M + Q, y = x + 1;
    for (auto &now : g[x]){
        if (now.first == y){
            now.second = W;
            break;
        }
    }
    for (auto &now : g[y]){
        if (now.first == x){
            now.second = W;
            break;
        }
    }
}

void changeV(int P, int Q, int W) {
    int x = P * M + Q, y = x + M;
    for (auto &now : g[x]){
        if (now.first == y){
            now.second = W;
            break;
        }
    }
}

int escape(int V1, int V2) {
    priority_queue<pair<int, int>> pq;
    pq.push(MP(0, V1));

    vector<int> d(N * M, 2e9 + 5);
    vector<bool> processed(N * M, false);
    d[V1] = 0;

    while (!pq.empty()){
        int x = pq.top().second; pq.pop();
        if (processed[x]) continue;
        processed[x] = true;
        for (auto edge : g[x]){
            int y = edge.first, w = edge.second;
            if (d[y] > d[x] + w){
                d[y] = d[x] + w;
                pq.push(MP(-d[y], y));
            }
        }
    }

    return d[(N - 1) * M + 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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 27852 KB Output is correct
2 Correct 69 ms 27904 KB Output is correct
3 Execution timed out 20022 ms 30500 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23756 KB Output is correct
2 Correct 12 ms 23800 KB Output is correct
3 Correct 11 ms 23756 KB Output is correct
4 Correct 29 ms 23804 KB Output is correct
5 Correct 17 ms 23800 KB Output is correct
6 Correct 20 ms 23792 KB Output is correct
7 Correct 28 ms 23756 KB Output is correct
8 Correct 25 ms 23860 KB Output is correct
9 Correct 28 ms 23856 KB Output is correct
10 Correct 26 ms 23792 KB Output is correct
11 Correct 6909 ms 26108 KB Output is correct
12 Correct 31 ms 23756 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 24536 KB Output is correct
2 Correct 189 ms 24624 KB Output is correct
3 Correct 137 ms 24544 KB Output is correct
4 Correct 141 ms 24560 KB Output is correct
5 Correct 138 ms 24536 KB Output is correct
6 Correct 12 ms 23756 KB Output is correct
7 Correct 13 ms 23728 KB Output is correct
8 Correct 12 ms 23712 KB Output is correct
9 Correct 185 ms 24584 KB Output is correct
10 Correct 12 ms 23756 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 361 ms 32056 KB Output is correct
2 Correct 870 ms 32048 KB Output is correct
3 Correct 367 ms 32056 KB Output is correct
4 Execution timed out 20060 ms 33328 KB Time limit exceeded

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 24524 KB Output is correct
2 Correct 187 ms 24636 KB Output is correct
3 Correct 137 ms 24524 KB Output is correct
4 Correct 143 ms 24548 KB Output is correct
5 Correct 136 ms 24524 KB Output is correct
6 Correct 366 ms 32056 KB Output is correct
7 Correct 851 ms 32036 KB Output is correct
8 Correct 363 ms 32064 KB Output is correct
9 Execution timed out 20040 ms 33072 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 24536 KB Output is correct
2 Correct 193 ms 24636 KB Output is correct
3 Correct 148 ms 24544 KB Output is correct
4 Correct 133 ms 24548 KB Output is correct
5 Correct 134 ms 24540 KB Output is correct
6 Correct 361 ms 32056 KB Output is correct
7 Correct 837 ms 31948 KB Output is correct
8 Correct 365 ms 31948 KB Output is correct
9 Execution timed out 20018 ms 33236 KB Time limit exceeded
10 Halted 0 ms 0 KB -