Submission #550462

#	Time	Username	Problem	Language	Result	Execution time	Memory
550462		PiejanVDC	Dungeons Game (IOI21_dungeons)	C++17	13 / 100	207 ms	54288 KiB

dungeons

#include <bits/stdc++.h>
#include "dungeons.h"

using namespace std;

int S;

const int mxN = (int)4e5+5;

int64_t jump[mxN][32];
int64_t win_jump[mxN][32];

int64_t val[mxN][32];
int64_t win_val[mxN][32];

int NN;

void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
    S = s[0];
    NN = n;
    for(int i = 0 ; i < n ; i++) {
        jump[i][0] = l[i];
        val[i][0] = p[i];
        win_jump[i][0] = w[i];
        win_val[i][0] = s[i];
    }
    jump[n][0] = n;
    win_jump[n][0] = n;
    for(int b = 1 ; b < 32 ; b++) {
        for(int i = 0 ; i <= n ; i++) {
            jump[i][b] = jump[jump[i][b-1]][b-1];
            win_jump[i][b] = win_jump[win_jump[i][b-1]][b-1];
            val[i][b] = val[i][b-1] + val[jump[i][b-1]][b-1];
            win_val[i][b] = win_val[i][b-1] + win_val[win_jump[i][b-1]][b-1];
        }
    }
}

long long simulate(int X, int Z) {
    int n = NN;
    long long x = X, z = Z;
    for(int s = 31 ; s >= 0 ; s--) {
        if(jump[x][s] == n) continue;
        if(z + val[x][s] < S) {
            z += val[x][s];
            x = jump[x][s];
        }
    }
    if(z < S) {
        z += val[x][0];
        x = jump[x][0];
    }
    for(int s = 31 ; s >= 0 ; s--) {
        if(win_jump[x][s] != n) {
            z += win_val[x][s];
            x = win_jump[x][s];
        }
    }
    if(x != n) {
        z += win_val[x][0];
        x = win_jump[x][0];
    }
	return z;
}

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