Submission #898978

#	Time	Username	Problem	Language	Result	Execution time	Memory
898978		Trisanu_Das	Dungeons Game (IOI21_dungeons)	C++17	63 / 100	1650 ms	1083380 KiB

dungeons

#include<bits/stdc++.h>
#include "dungeons.h"
using namespace std;

const int MAX_N = 50009;
int msh[MAX_N][26][26];
long long a, b, c, d, e, i, j, k, ii, jj, zx, xc, S[MAX_N], P[MAX_N], W[MAX_N], L[MAX_N], dis[MAX_N][26][26], mn[MAX_N][26][26], z;

void init(int Nn, vector<int> Ss, vector<int> Pp, vector<int> Ww, vector<int> Ll) {
    a = Nn;
    for (i = 0; i < a; i++) {
        S[i + 1] = Ss[i];
        P[i + 1] = Pp[i];
        W[i + 1] = Ww[i] + 1;
        L[i + 1] = Ll[i] + 1;
    }
    for (i = 1; i <= a; i++) {
        for (k = 0; k <= 24; k++) {
            if (S[i] < (1 << k)) {
                msh[i][0][k] = W[i];
                dis[i][0][k] = S[i];
                mn[i][0][k] = LLONG_MAX;
            } else {
                msh[i][0][k] = L[i];
                dis[i][0][k] = P[i];
                mn[i][0][k] = S[i];
            }
        }
    }

    for (j = 1; j <= 24; j++) {
        for (i = 1; i <= a; i++) {
            for (k = 0; k <= 24; k++) {
                msh[i][j][k] = msh[msh[i][j - 1][k]][j - 1][k];
                dis[i][j][k] = dis[i][j - 1][k] + dis[msh[i][j - 1][k]][j - 1][k];
                mn[i][j][k] = min(mn[i][j - 1][k], mn[msh[i][j - 1][k]][j - 1][k] - dis[i][j - 1][k]);
            }
        }
    }
}

long long simulate(int Xx, int Zz) {
    c = Xx + 1;
    z = Zz;
    while (c != a + 1) {
        for (k = 24; k >= 0; k--) if (z >= (1 << k)) break;
        for (j = 24; j >= 0; j--) {
            if (msh[c][j][k] == 0) continue;
            if (mn[c][j][k] > z) {
                z += dis[c][j][k];
                c = msh[c][j][k];
            }
        }
        if (c == a + 1) break;
        if (z >= S[c]) {
            z += S[c];
            c = W[c];
        } else {
            z += P[c];
            c = L[c];
        }
    }
    return z;
}

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