oj.uz

Submission #490910

# Submission time Handle Problem Language Result Execution time Memory
490910 2021-11-29T17:34:08 Z dxz05 Wombats (IOI13_wombats) C++14
0 / 100
 20000 ms 16624 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

int pref[MAXN];

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];
        }
        if (i < N - 1){
            pref[i] = VER[i][0];
            if (i > 0) pref[i] += pref[i - 1];
        }
    }

    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) {
    if (M == 1){
        return pref[V2 - 1] - (V1 > 0 ? pref[V1 - 1] : 0);
    }
    
    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:79:46: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   79 |             if (y >= N * M || x % M == M - 1 && dc[i] == 'R' || x % M == 0 && dc[i] == 'L') continue;
      |                               ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
wombats.cpp:79:76: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   79 |             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 4 ms 8140 KB Output is correct
2 Incorrect 4 ms 8160 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 0 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 716 KB Output is correct
2 Correct 171 ms 784 KB Output is correct
3 Correct 134 ms 696 KB Output is correct
4 Correct 124 ms 696 KB Output is correct
5 Correct 126 ms 708 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Incorrect 0 ms 204 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 494 ms 16036 KB Output is correct
2 Correct 1014 ms 16032 KB Output is correct
3 Correct 512 ms 16028 KB Output is correct
4 Execution timed out 20033 ms 16368 KB Time limit exceeded

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 716 KB Output is correct
2 Correct 185 ms 992 KB Output is correct
3 Correct 124 ms 716 KB Output is correct
4 Correct 122 ms 716 KB Output is correct
5 Correct 122 ms 716 KB Output is correct
6 Correct 505 ms 16032 KB Output is correct
7 Correct 1010 ms 16040 KB Output is correct
8 Correct 512 ms 16036 KB Output is correct
9 Execution timed out 20086 ms 16624 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 588 KB Output is correct
2 Correct 176 ms 796 KB Output is correct
3 Correct 126 ms 716 KB Output is correct
4 Correct 124 ms 588 KB Output is correct
5 Correct 125 ms 696 KB Output is correct
6 Correct 518 ms 16196 KB Output is correct
7 Correct 1004 ms 15948 KB Output is correct
8 Correct 504 ms 16156 KB Output is correct
9 Execution timed out 20059 ms 16544 KB Time limit exceeded
10 Halted 0 ms 0 KB -