Submission #592399

#	Time	Username	Problem	Language	Result	Execution time	Memory
592399		grt	Dungeons Game (IOI21_dungeons)	C++17	63 / 100	2737 ms	741292 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 = 50 * 1000 + 10, LOG = 25;
const ll INF = 1e18;
int n;
pair<int, ll>jp[nax][LOG][LOG];
ll lim[nax][LOG][LOG];
vi s, p, w, l;


void init(int N, vi _s, vi _p, vi _w, vi _l) {
        n = N;
        s = _s, w = _w, p = _p, l = _l;
        s.PB(n);
        for(int j = 0; j < LOG; ++j) {
            for(int i = 0; i < n; ++i) {
                        int num = (1 << j);
                        if(num >= s[i]) {
                            jp[i][j][0] = {w[i], s[i]};
                                lim[i][j][0] = INF;
                        } else {
                                jp[i][j][0] = {l[i], p[i]};
                                lim[i][j][0] = s[i];
                        }
        }
                jp[n][j][0] = {n, 0};
                lim[n][j][0] = INF;
        }
        for(int k = 1; k < LOG; ++k) {
                for(int j = LOG - 1; j >= 0; --j) {
                        for(int i = 0; i < n; ++i) {
                                auto [id, sum] = jp[i][j][k - 1];
                                lim[i][j][k] = min(lim[i][j][k - 1], lim[id][j][k - 1] - sum);
                                jp[i][j][k] = {jp[id][j][k - 1].ST, sum + jp[id][j][k - 1].ND};
                        }
                        jp[n][j][k] = {n, 0};
                        lim[n][j][k] = INF;
                }
        }
}

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);
                }
                for(int i = LOG - 1; i >= 0; --i) {
                        if(z < lim[x][bit][i]) {
                                z += jp[x][bit][i].ND;
                                x = jp[x][bit][i].ST;
                        }
                }
//              cerr << x << " " << z << "\n";
                if(x == n) {
                        return z;
                }
                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: 13 / 13
• Subtask 4: 12 / 12
• Subtask 5: 27 / 27
• Subtask 6: 0 / 11