Submission #1024083

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024083		mdn2002	Dungeons Game (IOI21_dungeons)	C++17	37 / 100	7085 ms	216320 KiB

dungeons

/*
Mayoeba Yabureru
*/
#include<bits/stdc++.h>
using namespace std;
long long power, st[400005][20], sum[400005][20], mx[400005][20];
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.clear();

    for (int i = 0; i < n; i ++) {
        st[i][0] = w[i];
        sum[i][0] = s[i];
        mx[i][0] = s[i];
    }
    st[n][0] = n;

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

long long simulate(int x, int z) {
    power = z;
    int cur = x;
    while (cur != n) {
        for (int i = 19; i >= 0; i --) {
            if (mx[cur][i] > power) continue;
            power += sum[cur][i];
            cur = st[cur][i];
        }
        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: 11 / 11
• Subtask 2: 26 / 26
• Subtask 3: 0 / 13
• Subtask 4: 0 / 12
• Subtask 5: 0 / 27
• Subtask 6: 0 / 11