Submission #550527

#	Time	Username	Problem	Language	Result	Execution time	Memory
550527		PiejanVDC	Dungeons Game (IOI21_dungeons)	C++17	24 / 100	7065 ms	427564 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;
bool T = 0; 

vector<int>sss,www,ppp,lll;

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;
   
    sss=s,www=w,ppp=p,lll=l;

    for(auto z : s)
	if(z != S)
	    T = 1;

    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) {
    if(T) {
	long long x = X, z = Z;
	while(x != NN) {
            if(z >= sss[x]) {
                z+=sss[x];
                x=www[x];
            } else {
                z+=ppp[x];
                x=lll[x];
            }
        }
        return 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: 11 / 11
• Subtask 2: 0 / 26
• Subtask 3: 13 / 13
• Subtask 4: 0 / 12
• Subtask 5: 0 / 27
• Subtask 6: 0 / 11