제출 #633694

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
633694		tabr	던전 (IOI21_dungeons)	C++17	100 / 100	2499 ms	1562764 KiB

dungeons

#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

// editorial

const int N = 400001;

int n;
int s[N];
int p[N];
int w[N];
int l[N];
vector<vector<int>> nxt[25];
vector<vector<int>> lim[25];
vector<vector<int>> inc[25];
/*
int nxt[25][25][N];
int lim[25][25][N];
int inc[25][25][N];
*/
long long d[N];

void init(int n_, vector<int> s_, vector<int> p_, vector<int> w_, vector<int> l_) {
    for (int i = 0; i < 25; i++) {
        nxt[i] = vector<vector<int>>(i + 1, vector<int>(N));
        lim[i] = vector<vector<int>>(i + 1, vector<int>(N));
        inc[i] = vector<vector<int>>(i + 1, vector<int>(N));
    }
    n = n_;
    for (int i = 0; i < n; i++) {
        s[i] = s_[i];
        p[i] = p_[i];
        w[i] = w_[i];
        l[i] = l_[i];
    }
    for (int i = n - 1; i >= 0; i--) {
        d[i] = d[w[i]] + s[i];
    }
    for (int i = 0; i < 25; i++) {
        for (int x = 0; x < n; x++) {
            if (s[x] >= (1 << i)) {
                nxt[i][0][x] = l[x];
                lim[i][0][x] = max(0, min((1 << (i + 1)) - p[x], s[x]));
                inc[i][0][x] = p[x];
            } else {
                nxt[i][0][x] = w[x];
                lim[i][0][x] = (1 << (i + 1)) - s[x];
                inc[i][0][x] = s[x];
            }
        }
        nxt[i][0][n] = n;
        for (int j = 1; j <= i; j++) {
            nxt[i][j][n] = n;
            for (int x = 0; x < n; x++) {
                int y = nxt[i][j - 1][x];
                nxt[i][j][x] = nxt[i][j - 1][y];
                lim[i][j][x] = max(0, min(lim[i][j - 1][x], lim[i][j - 1][y] - inc[i][j - 1][x]));
                inc[i][j][x] = min(1 << 27, inc[i][j - 1][x] + inc[i][j - 1][y]);
            }
        }
    }
}

long long simulate(int x, int z) {
    long long res = z;
    for (int i = 0; i < 25; i++) {
        if (x == n) {
            break;
        }
        if (res < (1 << i)) {
            if (res >= s[x]) {
                res += s[x];
                x = w[x];
            } else {
                res += p[x];
                x = l[x];
            }
        }
        assert(res >= (1 << i));
        for (int j = i; j >= 0; j--) {
            if (lim[i][j][x] > res) {
                res += inc[i][j][x];
                x = nxt[i][j][x];
            }
        }
    }
    res += d[x];
    return res;
}

#ifdef tabr
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    init(3, {2, 6, 9}, {3, 1, 2}, {2, 2, 3}, {1, 0, 1});
    debug(simulate(0, 1));  // 24
    debug(simulate(2, 3));  // 25
    return 0;
}
#endif

• Subtask 1: 11 / 11
• Subtask 2: 26 / 26
• Subtask 3: 13 / 13
• Subtask 4: 12 / 12
• Subtask 5: 27 / 27
• Subtask 6: 11 / 11