Submission #592266

#	Time	Username	Problem	Language	Result	Execution time	Memory
592266		grt	Dungeons Game (IOI21_dungeons)	C++17	0 / 100	606 ms	453880 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 = 24;
int n;
pair<int, ll>jp[nax][LOG][16];
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;
        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]};
                        } else {
                                jp[i][j][0] = {l[i], p[i]};
                        }
        }
                jp[n][j][0] = {n, 0};
        }
        for(int k = 1; k < 16; ++k) {
                for(int j = LOG - 1; j >= 0; --j) {
                        for(int i = 0; i < n; ++i) {
                                auto [id, sum] = jp[i][j][k - 1];
                                int num = (1 << j) + sum;
                                int bit = 31 - __builtin_clz(num);
                                jp[i][j][k] = {jp[id][bit][k - 1].ST, sum + jp[id][bit][k - 1].ND};
                        }
                        jp[n][j][k] = {n, 0};
                }
        }
}

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 = 15; i >= 0; --i) {
                        if(z + jp[x][bit][i].ND < (1 << (bit + 1))) {
                                z += jp[x][bit][i].ND;
                                x = jp[x][bit][i].ST;
                        }
                }
                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: 0 / 11
• Subtask 2: 0 / 26
• Subtask 3: 0 / 13
• Subtask 4: 0 / 12
• Subtask 5: 0 / 27
• Subtask 6: 0 / 11