Submission #1214341

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214341		omsincoconut	Dungeons Game (IOI21_dungeons)	C++17	13 / 100	162 ms	63544 KiB

dungeons

/*
Observation 1: After the first consecutive losses, you will lose at no more than O(log(s)) positions.
*/

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

using namespace std;
typedef long long ll;

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

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;

    // Initial losing
    for (int j = MAXBIT-1; j >= 0; j--) {
        if (loseval[j][x] > z && loseskip[j][x] != n) {
            z += losegain[j][x];
            x = loseskip[j][x];
        }
    }

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

    // Winning steps
    while (true) {
        if (z >= s[x] && w[x] == n) return z+s[x];
        if (z < s[x] && l[x] == n) return z+p[x];

        int targ;
        ll val;
        bool islose;
        if (z < s[x]) {
            targ = l[x];
            val = z + p[x];
            islose = true;
        } else {
            targ = w[x];
            val = z + s[x];
            islose = false;
        }

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

        int tx = targ;
        ll tz = val;
        for (int j = MAXBIT-1; j >= 0; j--) {
            if (loseval[j][tx] > z && loseskip[j][tx] != n) {
                tz += losegain[j][tx];
                tx = loseskip[j][tx];
            }
        }

        if (tz != val) {
            x = tx;
            z = tz;
            continue;
        }

        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 (targ == x && islose) {
            ll gain = val - z;
            ll iter = (s[x]-z+gain-1)/gain;
            z += gain*iter;
        } else {
            x = targ;
            z = val;
        }
    }
}

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