제출 #490923

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
490923		dxz05	웜뱃 (IOI13_wombats)	C++14	55 / 100	20044 ms	29760 KiB

wombats

#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(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(int x, char c){
    return get(x / M, x % M, c);
}

#define MP make_pair

int answer_sub1 = 0;

int dp[2][2][MAXN];

void calculate(){
    dp[0][0][0] = dp[1][1][0] = 0;
    dp[0][1][0] = dp[1][0][0] = HOR[0][0];

    for (int i = 1; i < N; i++){
        dp[0][0][i] = dp[0][1][i] = dp[1][0][i] = dp[1][1][i] = 2e9 + 5;

        for (int it = 0; it < 10; it++) {
            for (int j = 0; j < 2; j++) {
                for (int k = 0; k < 2; k++) {
                    dp[j][k][i] = min(dp[j][k][i], dp[j][k][i - 1] + VER[i - 1][k]);
                    dp[j][k][i] = min(dp[j][k][i], dp[j][k ^ 1][i] + HOR[i][0]);
                }
            }
        }
    }
}

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) answer_sub1 += VER[i][0];
    }

//    cerr << HOR[0][0] << endl;

    dv = {1, M, -1};

    if (M == 2) calculate();

}

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

void changeV(int P, int Q, int W) {
    answer_sub1 += W - VER[P][Q];
    VER[P][Q] = W;
    if (M == 2) calculate();
}

int escape(int V1, int V2) {
    if (M == 1) return answer_sub1;
    if (M == 2) return dp[V1][V2][N - 1];
    
    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(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];
}

컴파일 시 표준 에러 (stderr) 메시지

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

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 24