oj.uz

Submission #490906

# Submission time Handle Problem Language Result Execution time Memory
490906 2021-11-29T17:07:42 Z dxz05 Wombats (IOI13_wombats) C++14
28 / 100
 20000 ms 16516 KB 
#pragma GCC optimize("Ofast,O2,O3,unroll-loops")
#pragma GCC target("avx2")

#include "wombats.h"
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e6 + 3e2;

int HOR[5000][200], VER[5000][200];

int get_weight(int x, int y, char c){
//    if (c == 'U') return VER[x - 1][y];
    if (c == 'D') return VER[x][y];
    if (c == 'L') return HOR[x][y - 1];
    if (c == 'R') return HOR[x][y];
    assert(false);
    return -1;
}

vector<int> dv;
string dc = "RDL";

int N, M;

int get_weight(int x, char c){
    return get_weight(x / M, x % M, c);
}

#define MP make_pair

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; j++){
            if (j < M - 1) HOR[i][j] = _H[i][j];
            if (i < N - 1) VER[i][j] = _V[i][j];
        }
    }

    dv = {1, M, -1};

}

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

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

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 (int i = 0; i < 3; i++){
            int y = x + dv[i];

            if (y >= N * M || x % M == M - 1 && dc[i] == 'R' || x % M == 0 && dc[i] == 'L') continue;

            int w = get_weight(x, dc[i]);
            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;
      |      ^~~
wombats.cpp: In function 'int escape(int, int)':
wombats.cpp:69:46: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   69 |             if (y >= N * M || x % M == M - 1 && dc[i] == 'R' || x % M == 0 && dc[i] == 'L') continue;
      |                               ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
wombats.cpp:69:76: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   69 |             if (y >= N * M || x % M == M - 1 && dc[i] == 'R' || x % M == 0 && dc[i] == 'L') continue;
      |                                                                 ~~~~~~~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 8164 KB Output is correct
2 Correct 80 ms 8148 KB Output is correct
3 Execution timed out 20003 ms 9172 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 16 ms 384 KB Output is correct
5 Correct 10 ms 380 KB Output is correct
6 Correct 9 ms 332 KB Output is correct
7 Correct 18 ms 332 KB Output is correct
8 Correct 13 ms 376 KB Output is correct
9 Correct 15 ms 332 KB Output is correct
10 Correct 13 ms 388 KB Output is correct
11 Correct 7545 ms 1296 KB Output is correct
12 Correct 19 ms 332 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 588 KB Output is correct
2 Correct 173 ms 768 KB Output is correct
3 Correct 128 ms 700 KB Output is correct
4 Correct 121 ms 692 KB Output is correct
5 Correct 121 ms 588 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 180 ms 696 KB Output is correct
10 Correct 0 ms 204 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 496 ms 16004 KB Output is correct
2 Correct 985 ms 16008 KB Output is correct
3 Correct 513 ms 16012 KB Output is correct
4 Execution timed out 20094 ms 16284 KB Time limit exceeded

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 588 KB Output is correct
2 Correct 178 ms 928 KB Output is correct
3 Correct 129 ms 688 KB Output is correct
4 Correct 124 ms 588 KB Output is correct
5 Correct 131 ms 684 KB Output is correct
6 Correct 533 ms 16004 KB Output is correct
7 Correct 1014 ms 16004 KB Output is correct
8 Correct 528 ms 16008 KB Output is correct
9 Execution timed out 20074 ms 16312 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 684 KB Output is correct
2 Correct 171 ms 784 KB Output is correct
3 Correct 125 ms 700 KB Output is correct
4 Correct 122 ms 588 KB Output is correct
5 Correct 122 ms 684 KB Output is correct
6 Correct 490 ms 15948 KB Output is correct
7 Correct 981 ms 16000 KB Output is correct
8 Correct 508 ms 16000 KB Output is correct
9 Execution timed out 20041 ms 16516 KB Time limit exceeded
10 Halted 0 ms 0 KB -