Submission #1062828

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062828		TheQuantiX	Dungeons Game (IOI21_dungeons)	C++17	50 / 100	7040 ms	873060 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;
vector<ll> wup[30];
vector<ll> wupmx[30];
vector<ll> wupm[30];
vector<ll> lup[30];
vector<ll> lupmn[30];
vector<ll> lupm[30];

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] - 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]];
        }
    }
    for (int i = 0; i < 30; i++) {
        wup[i].resize(n + 1);
        wupmx[i].resize(n + 1);
        wupm[i].resize(n + 1);
        lup[i].resize(n + 1);
        lupmn[i].resize(n + 1);
        lupm[i].resize(n + 1);
        if (i == 0) {
            for (int j = 0; j < n; j++) {
                wupm[i][j] = w[j];
                wup[i][j] = s[j];
                wupmx[i][j] = s[j] * 2 - wup[i][j];
                lupm[i][j] = l[j];
                lup[i][j] = p[j];
                lupmn[i][j] = s[j];
            }
            wupm[i][n] = n;
            wupmx[i][n] = 0;
            wup[i][n] = 0;
            lupm[i][n] = n;
            lupmn[i][n] = 0;
            lup[i][n] = 0;
        }
        else {
            for (int j = 0; j < n + 1; j++) {
                wupm[i][j] = wupm[i - 1][wupm[i - 1][j]];
                wup[i][j] = wup[i - 1][j] + wup[i - 1][wupm[i - 1][j]];
                wupmx[i][j] = max(wupmx[i - 1][j], wupmx[i - 1][wupm[i - 1][j]] - wup[i - 1][j]);
                lupm[i][j] = lupm[i - 1][lupm[i - 1][j]];
                lup[i][j] = lup[i - 1][j] + lup[i - 1][lupm[i - 1][j]];
                lupmn[i][j] = min(lupmn[i - 1][j], lupmn[i - 1][lupm[i - 1][j]] - lup[i - 1][j]);
            }
        }
    }
}

long long simulate2(int x, ll z);

long long simulate3(int x, ll z);

long long simulateult(int x, ll z);

long long simulate(int x, int z) {
    return simulateult(x, 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;
}

long long simulateult(int x, ll z) {
    // cout << x << endl;
    while (x < n) {
        // cout << x << ' ' << z << '\n';
        if (z >= s[x]) {
            for (int i = 29; i >= 0; i--) {
                // cout << '\t' << i << ' ' << wupmx[i][x] << '\n';
                if (wupmx[i][x] <= z) {
                    z += wup[i][x];
                    x = wupm[i][x];
                }
            }
        }
        else {
            for (int i = 29; i >= 0; i--) {
                // cout << '\t' << i << ' ' << lupmn[i][x] << '\n';
                if (lupmn[i][x] > z) {
                    z += lup[i][x];
                    x = lupm[i][x];
                }
            }
        }
        if (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;
}

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