Submission #1062533

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062533		TheQuantiX	Dungeons Game (IOI21_dungeons)	C++17	11 / 100	7050 ms	24104 KiB

dungeons

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

ll n, m, q, k, x, y, a, b, c;
vector<int> s, p, w, l;
bool testcase3;
vector<ll> up[30];
vector<ll> upm[30];
vector<ll> wins;

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;
    set<ll> st;
    for (int i = 0; i < n; i++) {
        st.insert(s[i]);
    }
    if (st.size() == 1) {
        testcase3 = 1;
        for (int i = 0; i < 30; i++) {
            up[i].resize(n);
            upm[i].resize(n);
            if (i == 0) {
                for (int j = 0; j < n; j++) {
                    upm[i][j] = l[j];
                    up[i][j] = p[j];
                }
            }
            else {
                for (int j = 0; j < n; j++) {
                    upm[i][j] = upm[i - 1][upm[i - 1][j]];
                    up[i][j] = up[i - 1][j] + up[i - 1][upm[i - 1][j]];
                }
            }
        }
        wins.resize(n + 1);
        for (int i = n - 1; i >= 0; i--) {
            wins[i] = s[i] + wins[w[i]];
        }
    }
}

long long simulate3(int x, int z);

long long simulate(int x, int z) {
    if (testcase3) {
        return simulate3(x, z);
    }
    while (x < n) {
        if (z >= s[x]) {
            z += s[x];
            x = w[x];
        }
        else {
            z += p[x];
            x = l[x];
        }
        // cout << x << ' ' << z << '\n';
    }
    return z;
}

long long simulate3(int x, int z) {
    for (int i = 29; i >= 0; i--) {
        // cout << i << ' ' << up[i][x] << '\n';
        if (z + up[i][x] < s[0]) {
            // cout << z + up[i][x] << '\n';
            z += up[i][x];
            x = upm[i][x];
            // cout << x << ' ' << z << '\n';
        }
    }
    z += p[x];
    x = l[x];
    // cout << x << ' ' << z << '\n';
    z += wins[x];
    // cout << n << ' ' << z << '\n';
    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