제출 #793760

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
793760		resting	던전 (IOI21_dungeons)	C++17	100 / 100	2876 ms	210876 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;

#define  int long long
const int inf = 1e15;
int n; vector<int32_t> s, p, w, l;

const int mx = 4e5 + 5;
struct uwu {
    int jump;
    int thresh;
    int ad;
    int dep;
    int par;
} to[mx][9];

vector<vector<int>> rev;
vector<int> vis, vis2;
int thresh;

void init(int32_t nn, std::vector<int32_t> ss, std::vector<int32_t> pp, std::vector<int32_t> ww, std::vector<int32_t> ll) {
    n = nn; s = ss; p = pp; w = ww; l = ll;
    for (int i = 0; i < 9; i++) {
        thresh = (1 << (3 * i));
        vis = vis2 = vector<int>(n, 0);
        rev = vector<vector<int>>(n);
        for (int j = 0; j < n; j++) {
            if (thresh >= s[j]) {
                to[j][i].par = w[j];if (w[j] != n)rev[w[j]].push_back(j);
            } else {
                to[j][i].par = l[j];if (l[j] != n)rev[l[j]].push_back(j);
            }

        }
        for (int j = 0; j < n; j++) {
            if (vis2[j]) continue;
            int t = j;
            while (1) {
                vis[t] = 1;
                if (to[t][i].par == n || vis[to[t][i].par]) break;
                t = to[t][i].par;
            }
            int rt = t;
            to[t][i].jump = to[t][i].thresh = to[t][i].ad = -1; to[t][i].dep = 0;
            if (to[t][i].par != n) {
                int curthresh = inf;
                int cursm = 0;
                while (1) {
                    if (!vis[t]) break;
                    vis[t] = 0;
                    if (thresh < s[t]) {
                        curthresh = min(curthresh, s[t] - cursm);
                    }
                    cursm += thresh >= s[t] ? s[t] : p[t];
                    t = to[t][i].par;
                }
                to[t][i].jump = t; to[t][i].thresh = curthresh; to[t][i].ad = cursm;
            }
            vector<int> st; st.push_back(t);
            while (!st.empty()) {
                int t2 = st.back(); st.pop_back();
                if (vis2[t2]) continue;
                vis2[t2] = 1; for (auto& x : rev[t2]) st.push_back(x);
                if (t2 == rt) {
                    continue;
                }
                to[t2][i].dep = to[to[t2][i].par][i].dep + 1;
                to[t2][i].thresh = thresh >= s[t2] ? inf : s[t2];
                to[t2][i].ad = thresh >= s[t2] ? s[t2] : p[t2];
                to[t2][i].jump = to[t2][i].par;
                if (rt == to[t2][i].par) {
                } else if (rt == to[to[t2][i].par][i].jump) {
                } else if (to[to[to[t2][i].par][i].jump][i].dep - to[to[t2][i].par][i].dep == to[to[to[to[t2][i].par][i].jump][i].jump][i].dep - to[to[to[t2][i].par][i].jump][i].dep) {
                    to[t2][i].jump = to[to[to[t2][i].par][i].jump][i].jump;
                    to[t2][i].thresh = min(to[t2][i].thresh, min(to[to[t2][i].par][i].thresh - to[t2][i].ad, to[to[to[t2][i].par][i].jump][i].thresh - to[to[t2][i].par][i].ad - to[t2][i].ad));
                    to[t2][i].ad += to[to[to[t2][i].par][i].jump][i].ad + to[to[t2][i].par][i].ad;
                }
            }
        }
    }
    return;
}

long long simulate(int32_t xx, int32_t zz) {
    int cur = 0;
    int x = xx; int z = zz;
    while (x != n) {
        while (cur + 1 < 9 && z >= (1LL << (3 * (cur + 1)))) cur++;
        if (z < to[x][cur].thresh) {
            if (to[x][cur].jump == x) {
                int k = (to[x][cur].thresh - z + to[x][cur].ad - 1) / to[x][cur].ad;
                z += to[x][cur].ad * k;
            } else {
                z += to[x][cur].ad;  x = to[x][cur].jump;
            }
        } else {
            if (z >= s[x]) {
                z += s[x]; x = w[x];
            } else {
                z += p[x]; x = l[x];
            }
        }
    }
    return z;
}

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