Submission #542926

#	Time	Username	Problem	Language	Result	Execution time	Memory
542926		alextodoran	Dungeons Game (IOI21_dungeons)	C++17	37 / 100	7058 ms	2063604 KiB

dungeons

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 400000;
const int N_BITS = 25;
const int S_QITS = 13;

int N;
int strength[N_MAX];
int winBonus[N_MAX];
int loseBonus[N_MAX];
int winEdge[N_MAX];
int loseEdge[N_MAX];

int last[N_MAX + 1][S_QITS][N_BITS];
ll bonus[N_MAX + 1][S_QITS][N_BITS];
int maxDiff[N_MAX + 1][S_QITS][N_BITS];
// maximum (bonus - strength) at some moment when we lost

void init (int _N, vector <int> _S, vector <int> _P, vector <int> _W, vector <int> _L) {
    // Transfer input to global
    N = _N;
    for (int u = 0; u < N; u++) {
        strength[u] = _S[u];
        winBonus[u] = _S[u];
        loseBonus[u] = _P[u];
        winEdge[u] = _W[u];
        loseEdge[u] = _L[u];
    }
    // Precompute jumps
    for (int sqit = 0; sqit < S_QITS; sqit++) {
        for (int nbit = 0; nbit < N_BITS; nbit++) {
            last[N][sqit][nbit] = N;
            bonus[N][sqit][nbit] = 0;
            maxDiff[N][sqit][nbit] = INT_MIN;
        }
    }
    for (int u = 0; u < N; u++) {
        for (int sqit = 0; sqit < S_QITS; sqit++) {
            if ((1 << (sqit * 2)) > strength[u]) {
                last[u][sqit][0] = winEdge[u];
                bonus[u][sqit][0] = winBonus[u];
                maxDiff[u][sqit][0] = INT_MIN;
            } else {
                last[u][sqit][0] = loseEdge[u];
                bonus[u][sqit][0] = loseBonus[u];
                maxDiff[u][sqit][0] = 0 - strength[u];
            }
        }
    }
    for (int nbit = 1; nbit < N_BITS; nbit++) {
        for (int u = 0; u < N; u++) {
            for (int sqit = 0; sqit < S_QITS; sqit++) {
                int v = last[u][sqit][nbit - 1];
                last[u][sqit][nbit] = last[v][sqit][nbit - 1];
                bonus[u][sqit][nbit] = bonus[u][sqit][nbit - 1] + bonus[v][sqit][nbit - 1];
                maxDiff[u][sqit][nbit] = min((ll) 0, max((ll) maxDiff[u][sqit][nbit - 1],
                                             bonus[u][sqit][nbit - 1] + maxDiff[v][sqit][nbit - 1]));
            }
        }
    }
}

ll simulate (int u, int initStrength) {
    ll currStrength = initStrength;
    while (true) {
        for (int nbit = N_BITS - 1; nbit >= 0; nbit--) {
            int sqit = 0;
            while (sqit + 1 < S_QITS && (1 << ((sqit + 1) * 2)) <= currStrength) {
                sqit++;
            }
            int maxd = maxDiff[u][sqit][nbit];
            if (u < N && (maxd == INT_MIN || currStrength + maxd < 0)) {
                currStrength += bonus[u][sqit][nbit];
                u = last[u][sqit][nbit];
            }
        }
        if (u == N) {
            break;
        }
        if (currStrength >= strength[u]) {
            currStrength += winBonus[u];
            u = winEdge[u];
        } else {
            currStrength += loseBonus[u];
            u = loseEdge[u];
        }
    }
    return currStrength;
}

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