Submission #1214432

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214432		omsincoconut	Dungeons Game (IOI21_dungeons)	C++17	50 / 100	423 ms	489660 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int n;
vector<int> s, p, w, l;

const ll INF = 1e18;

const int MAXBIT = 30, MAXN = 4e5+5;
int winskip[MAXBIT][MAXN], loseskip[MAXBIT][MAXN];
ll winval[MAXBIT][MAXN], loseval[MAXBIT][MAXN], wingain[MAXBIT][MAXN], losegain[MAXBIT][MAXN];

void init(int _n, vector<int> _s, vector<int> _p, vector<int> _w, vector<int> _l) {
    n = _n; s = _s; p = _p; w = _w; l = _l;

    s.push_back(0); p.push_back(0); w.push_back(n); l.push_back(n);

    for (int i = 0; i <= n; i++) {
        winskip[0][i] = w[i];
        winval[0][i] = s[i];
        wingain[0][i] = s[i];

        loseskip[0][i] = l[i];
        loseval[0][i] = s[i];
        losegain[0][i] = p[i];
    }

    for (int j = 0; j < MAXBIT-1; j++) {
        for (int i = 0; i <= n; i++) {
            int skw = winskip[j][i];
            winskip[j+1][i] = winskip[j][skw];
            winval[j+1][i] = max(winval[j][i], winval[j][skw] - wingain[j][i]);
            wingain[j+1][i] = wingain[j][i] + wingain[j][skw];

            int skl = loseskip[j][i];
            loseskip[j+1][i] = loseskip[j][skl];
            loseval[j+1][i] = min(loseval[j][i], loseval[j][skl] - losegain[j][i]);
            losegain[j+1][i] = losegain[j][i] + losegain[j][skl];
        }
    }
}

long long simulate(int x, int _z) {
    ll z = _z;

    // Winning steps
    int cnt = 0;
    while (true) {
        cnt ++;
        assert(cnt < 100);
        int targ = x;
        ll val = z;

        if (val >= s[targ] && w[targ] == n) return val+s[targ];
        if (val < s[targ] && l[targ] == n) return val+p[targ];

        ll minlose = INF, summed = 0;
        bool havelose = false;
        for (int j = MAXBIT-1; j >= 0; j--) {
            if (loseval[j][targ] > val && loseskip[j][targ] != n) {
                val += losegain[j][targ];
                minlose = min(minlose, loseval[j][targ] - summed);
                summed += losegain[j][targ];
                targ = loseskip[j][targ];
                havelose = true;
            }
        }

        if (val >= s[targ] && w[targ] == n) return val+s[targ];
        if (val < s[targ] && l[targ] == n) return val+p[targ];

        for (int j = MAXBIT-1; j >= 0; j--) {
            if (winval[j][targ] <= val && winskip[j][targ] != n) {
                val += wingain[j][targ];
                targ = winskip[j][targ];
            }
        }

        if (val >= s[targ] && w[targ] == n) return val+s[targ];
        if (val < s[targ] && l[targ] == n) return val+p[targ];

        if (minlose > z && havelose && targ == x) {
            ll gain = val-z;
            ll iter = (minlose-z+gain-1)/gain;
            z += gain*iter;
        } else {
            x = targ;
            z = val;
        }
    }
}

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