Submission #592589

#	Time	Username	Problem	Language	Result	Execution time	Memory
592589		grt	Dungeons Game (IOI21_dungeons)	C++17	11 / 100	7107 ms	847340 KiB

dungeons

//GRT_2018
#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second
//mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

using namespace std;

using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;

const int nax = 400 * 1000 + 10, LOG = 25;
const ll INF = 1e18;
int n;
vi s, p, w, l;
int pr[nax][LOG], val[nax][LOG];
ll lim[nax][LOG];
int deg[nax];
vector<int>T[nax][LOG];
tuple<int,ll,ll>jp[nax][LOG];
int dep[nax];

void dfs(int x, int lvl) {
        for(int y : T[x][lvl]) {
                dep[y] = dep[x] + 1;
                if(dep[x] - dep[get<0>(jp[x][lvl])] == dep[get<0>(jp[x][lvl])] - dep[get<0>(jp[get<0>(jp[x][lvl])][lvl])]) {
                        auto [id1, s1, l1] = jp[x][lvl];
                        auto [id2, s2, l2] = jp[id1][lvl];
                        jp[y][lvl] = {id2, s1 + s2 + val[y][lvl], min({l2 - s1 - val[y][lvl], l1 - val[y][lvl], lim[y][lvl]})};
         } else {
                        jp[y][lvl] = {x, val[y][lvl], lim[y][lvl]};
                }
                dfs(y, lvl);
        }
}


bool root[nax][LOG];

void init(int N, vi _s, vi _p, vi _w, vi _l) {
        n = N;
        s = _s, w = _w, p = _p, l = _l;
        for(int j = 0; j < LOG; ++j) {
                for(int i = 0; i <= n; ++i) deg[i] = 0;
                for(int i = 0; i < n; ++i) {
                        int num = (1 << j);
                        if(num >= s[i]) {
                                pr[i][j] = w[i];
                                deg[w[i]]++;
                                val[i][j] = s[i];
                                lim[i][j] = INF;
                        } else {
                                pr[i][j] = l[i];
                                deg[l[i]]++;
                                val[i][j] = p[i];
                                lim[i][j] = s[i];
                        }
        }
                deg[n]++;
                queue<int>Q;
                for(int i = 0; i <= n; ++i) {
                        if(deg[i] == 0) Q.push(i);
                }
                while(!Q.empty()) {
                        int x = Q.front();
                        Q.pop();
                        deg[pr[x][j]]--;
                        T[pr[x][j]][j].PB(x);
                        if(deg[pr[x][j]] == 0) {
                                Q.push(pr[x][j]);
                        }
                }
                for(int i = 0; i <= n; ++i) {
                        if(deg[i] > 0) {
                                jp[i][j] = {i, 0, INF};
                                dep[i] = 0;
                                val[i][j] = 0;
                                lim[i][j] = INF;
                                pr[i][j] = i;
                                dfs(i, j);
                                root[i][j] = true;
                        }
                }

        }
}

ll simulate(int x, int zz) {
        int inf = 10'000'000;
        ll z = zz;
        while(x != n) {
                int bit = LOG - 1;
                if(z < inf) {
                        bit = 31 - __builtin_clz(z);
                }
                while(!root[x][bit]) {
                        if(z < get<2>(jp[x][bit])) {
                                z += get<1>(jp[x][bit]);
                                x = get<0>(jp[x][bit]);
                        } else if(z < lim[x][bit]) {
                                z += val[x][bit];
                                x = pr[x][bit];
                        } else {
                                break;
                        }
                }
                if(x == n) {
                        return z;
                }
                // i am on the cycle
                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: 0 / 26
• Subtask 3: 0 / 13
• Subtask 4: 0 / 12
• Subtask 5: 0 / 27
• Subtask 6: 0 / 11