Submission #1062767

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062767		TheQuantiX	Dungeons Game (IOI21_dungeons)	C++17	50 / 100	7066 ms	310352 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, testcase2;
vector<ll> up[30];
vector<ll> upmx[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;
    testcase2 = 1;
    set<ll> st;
    for (int i = 0; i < n; i++) {
        if (s[i] != p[i]) {
            testcase2 = 0;
        }
        st.insert(s[i]);
    }
    if (testcase2) {
        for (int i = 0; i < 30; i++) {
            up[i].resize(n + 1);
            upmx[i].resize(n + 1);
            upm[i].resize(n + 1);
            if (i == 0) {
                for (int j = 0; j < n; j++) {
                    upm[i][j] = w[j];
                    up[i][j] = s[j];
                    upmx[i][j] = s[j] * 2 - up[i][j];
                }
                upm[i][n] = n;
                upmx[i][n] = 0;
                up[i][n] = 0;
            }
            else {
                for (int j = 0; j < n + 1; 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]];
                    upmx[i][j] = max(upmx[i - 1][j], upmx[i - 1][upm[i - 1][j]] - up[i - 1][j]);
                }
            }
        }
    }
    else if (st.size() == 1) {
        testcase3 = 1;
        for (int i = 0; i < 30; i++) {
            up[i].resize(n + 1);
            upm[i].resize(n + 1);
            if (i == 0) {
                for (int j = 0; j < n; j++) {
                    upm[i][j] = l[j];
                    up[i][j] = p[j];
                }
                upm[i][n] = n;
                up[i][n] = 0;
            }
            else {
                for (int j = 0; j < n + 1; 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]];
                }
            }
        }
        // cout << "DEBUG" << endl;
        wins.resize(n + 1);
        for (int i = n - 1; i >= 0; i--) {
            // cout << i << ' ' << s[i] << endl;
            wins[i] = s[i] + wins[w[i]];
        }
    }
}

long long simulate2(int x, ll z);

long long simulate3(int x, ll z);

long long simulate(int x, int z) {
    if (testcase2) {
        return simulate2(x, 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 simulate2(int x, ll z) {
    while (x < n) {
        for (int i = 29; i >= 0; i--) {
            // cout << i << ' ' << up[i][x] << '\n';
            if (upmx[i][x] <= z) {
                z += up[i][x];
                x = upm[i][x];
            }
        }
        if (x != n) {
            z += p[x];
            x = l[x];
        }
    }
    return z;
}

long long simulate3(int x, ll z) {
    for (int i = 29; i >= 0; i--) {
        // cout << i << ' ' << up[i][x] << '\n';
        if (z + up[i][x] < s[0] && upm[i][x] != n) {
            // cout << z + up[i][x] << '\n';
            z += up[i][x];
            x = upm[i][x];
            // cout << x << ' ' << z << '\n';
        }
    }
    if (z < s[0]) {
        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: 26 / 26
• Subtask 3: 13 / 13
• Subtask 4: 0 / 12
• Subtask 5: 0 / 27
• Subtask 6: 0 / 11