Submission #1024099

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024099		mdn2002	Dungeons Game (IOI21_dungeons)	C++17	0 / 100	158 ms	323772 KiB

dungeons

/*
Mayoeba Yabureru
*/
#include<bits/stdc++.h>
using namespace std;
long long power, st[50004][20][10], sum[50004][20][10], done[10];
vector<long long> values;
int n, q;
vector<int> s, p, z, w, l, x;

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;
    values.push_back(1e16);
    for (int i = 0; i < n; i ++) values.push_back(s[i]);
    sort(values.begin(), values.end());
}

void initst() {
    int order = upper_bound(values.begin(), values.end(), power) - values.begin();

    for (int i = 0; i < n; i ++) {
        if (power >= s[i]) {
            st[i][0][order] = w[i];
            sum[i][0][order] = s[i];
        }
        else {
            st[i][0][order] = l[i];
            sum[i][0][order] = p[i];
        }
    }
    st[n][0][order] = n;

    for (int i = 1; i < 20; i ++) {
        for (int j = 0; j <= n; j ++) {
            st[j][i][order] = st[st[j][i - 1][order]][i - 1][order];
            sum[j][i][order] = sum[j][i - 1][order] + sum[st[j][i - 1][order]][i - 1][order];
        }
    }
    done[order] = 1;
}

long long simulate(int x, int z) {
    power = z;
    int cur = x;
    while (cur != n) {
        initst();
        int order = upper_bound(values.begin(), values.end(), power) - values.begin();


        for (int i = 19; i >= 0; i --) {
            if (values[order] <= power + sum[cur][i][order]) continue;
            power += sum[cur][i][order];
            cur = st[cur][i][order];
        }
        if (cur == n) break;
        if (s[cur] > power) {
            power += p[cur];
            cur = l[cur];
        }
        else {
            power += s[cur];
            cur = w[cur];
        }
    }
    return power;
}

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