Submission #560077

#	Time	Username	Problem	Language	Result	Execution time	Memory
560077		nghiass001	Dungeons Game (IOI21_dungeons)	C++17	26 / 100	907 ms	387636 KiB

dungeons

#include <bits/stdc++.h>
#define FOR(i,l,r) for(int i=(l); i<=(r); ++i)
#define REP(i,l,r) for(int i=(l); i<(r); ++i)
#define FORD(i,r,l) for(int i=(r); i>=(l); --i)
#define REPD(i,r,l) for(int i=(r)-1; i>=(l); --i)
using namespace std;
const int N = 4e5 + 5, logN = 19;
int nn, lose[N], next_win[N], next_los[N];
long long strong[N];
long long pwin[N][logN], pwinmax[N][logN], sumwin[N][logN];
long long plos[N][logN], plosmin[N][logN], sumlos[N][logN];
set<long long> ST;

void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
    nn = n;
    REP(i, 0, nn) {
        strong[i] = s[i];
        lose[i] = p[i];
        next_win[i] = w[i];
        next_los[i] = l[i];
    }
    next_win[nn] = nn;
    next_los[nn] = nn;

    REP(i, 0, nn) pwin[i][0] = next_win[i];
    FOR(i, 0, nn) {
        pwin[i][0] = next_win[i];
        plos[i][0] = next_los[i];
        pwinmax[i][0] = strong[i];
        plosmin[i][0] = strong[i];
        sumwin[i][0] = s[i];
        sumlos[i][0] = lose[i];
    }

    REP(j, 1, logN) {
        FOR(i, 0, nn) {
            pwin[i][j] = pwin[pwin[i][j - 1]][j - 1];
            plos[i][j] = plos[plos[i][j - 1]][j - 1];
            pwinmax[i][j] = max(pwinmax[i][j - 1], pwinmax[pwin[i][j - 1]][j - 1] - sumwin[i][j - 1]);
            plosmin[i][j] = min(plosmin[i][j - 1], plosmin[plos[i][j - 1]][j - 1] - sumlos[i][j - 1]);
            sumwin[i][j] = sumwin[i][j - 1] + sumwin[pwin[i][j - 1]][j - 1];
            sumlos[i][j] = sumlos[i][j - 1] + sumlos[plos[i][j - 1]][j - 1];
        }
    }
    FOR(i, 0, nn) ST.insert(strong[i]);
}

int iTest;
long long avail[N], old_val[N];

long long simulate(int x, int strong_root) {
    long long my_strong = strong_root;
    ++iTest;

    static bool WIN = 1, LOSE = 0;
    bool type = WIN;
    while (x != nn) {
        if (type == WIN) {
            REPD(i, logN, 0) {
                if (pwinmax[x][i] <= my_strong) {
                    my_strong += sumwin[x][i];
                    x = pwin[x][i];
                }
            }
            type = LOSE;
        }
        else if (type == LOSE) {
            if (avail[x] != iTest) {
                avail[x] = iTest;
                old_val[x] = -1;
            }
            if (ST.upper_bound(old_val[x]) == ST.upper_bound(my_strong)) {
                long long diff = my_strong - old_val[x];
                long long tmp = *ST.upper_bound(my_strong);
                long long cnt = tmp / diff;
                my_strong += cnt * diff;
            }
            old_val[x] = my_strong;

            REPD(i, logN, 0) {
                if (plosmin[x][i] > my_strong) {
                    my_strong += sumlos[x][i];
                    x = plos[x][i];
                }
            }
            type = WIN;
        }
    }
    return my_strong;
}

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