Submission #1067434

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067434		Itamar	Dungeons Game (IOI21_dungeons)	C++17	63 / 100	2734 ms	983088 KiB

dungeons

#include <vector>
using namespace std;
#define vi vector<int> 
#define ll long long
vi S,P,W,L;
int N;
const int siz = 5e4+2;
#include<iostream>
// tos + Z >= S[i]
// assuming 2^k <= Z < 2^(k+1) in all jumps
ll dp[siz][30][30]; // minumum of S[i]-tos 
ll tos[siz][30][30];
int wer[siz][30][30];
void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
	S=s,P=p,W=w,L=l,N=n;
		
	for(int k = 0; k < 30; k++){
		for(int i = 0; i < n; i++){
			if(S[i] > (1<<k)){
				wer[i][0][k] = l[i];
				tos[i][0][k] = p[i];
				dp[i][0][k] = S[i];
			}else{
				wer[i][0][k] = w[i];
				tos[i][0][k] = S[i];
				dp[i][0][k] = 1e18;
			}
		}
		for(int j = 1; j < 30; j++){
			for(int i = 0; i < n; i++){
				wer[i][j][k] = wer[wer[i][j-1][k]][j-1][k];
				int ind = wer[i][j-1][k];
				tos[i][j][k] = tos[i][j-1][k] + tos[ind][j-1][k];
				dp[i][j][k] = min(dp[i][j-1][k], dp[ind][j-1][k]-tos[i][j-1][k]);
			}
			wer[n][j][k]=n;
		}
	}
}

long long simulate(int x, int z) {
	ll Z = z;
	int k = 0;
	while((1<<(k+1)) <= Z)k++;
	while(x<N){
		for(int j = 29; j>=0; j--){
			if(wer[x][j][k] < N && dp[x][j][k]>Z){
				Z+= tos[x][j][k];
				x = wer[x][j][k];
			}
		}

		if(Z < S[x]){
			Z += P[x];
			x = L[x];
		}else{
			Z += S[x];
			x = W[x];
		}
		if(x==N)return Z;
		if(Z < S[x]){
			Z += P[x];
			x = L[x];
		}else{
			Z += S[x];
			x = W[x];
		}
		k++;
	}
	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