Submission #793721

#	Time	Username	Problem	Language	Result	Execution time	Memory
793721		resting	Dungeons Game (IOI21_dungeons)	C++17	37 / 100	7089 ms	461360 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][25];
const int x = sizeof(to);
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 < 25; i++) {
        thresh = (1 << 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];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;
            //     }
            //     assert(t == rt);
            //     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;
                }
            }
        }
        //cout << "iter: " << i << endl;
        // for (int j = 0; j < n; j++) {
        //     cout << "dep: " << to[j][i].dep << "   ad: " << to[j][i].ad << "   jump: " << to[j][i].jump << "   thresh: " << to[j][i].thresh << "    par: " << to[j][i].par << endl;
        // }
    }
    return;
}

long long simulate(int32_t xx, int32_t zz) {
    int cur = 0;
    int x = xx; int z = zz;
    while (x != n) {
        //cout << x << "," << z << "," << cur << endl;
        while (cur + 1 < 25 && z >= (1LL << (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;
}

// int32_t main() {
//     init(3, { 2, 6, 9 }, { 3, 1,2 }, { 2, 2, 3 }, { 1, 0, 1 });
//     cout << simulate(0, 1) << endl;
// }

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