Submission #1067254

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067254		Itamar	Dungeons Game (IOI21_dungeons)	C++17	0 / 100	62 ms	44812 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 = 5e5;
#include<iostream>
ll bin[siz][30];
ll tos[siz][30];
int wer[siz][30];
int wer2[siz][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 i = 0; i < n; i++){
		bin[i][0] = s[i];
		tos[i][0] = p[i];
		wer[i][0] = l[i];
		wer2[i][0] = w[i];
	}

	wer[n][0]=n;
	wer2[n][0]=n;
	for(int j = 1; j < 30; j++){
		for(int i = 0; i < n; i++){
			wer[i][j] = wer[wer[i][j-1]][j-1];
			int ind = wer[i][j-1];
			tos[i][j] = tos[i][j-1] + tos[ind][j-1];
			bin[i][j] = max(bin[i][j-1],bin[ind][j-1]-tos[i][j-1]);
			wer2[i][j] = wer2[wer2[i][j-1]][j-1];
		}
		wer[n][j]=n;
		wer2[n][j]=n;
	}
}

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

		if(Z < S[x]){
			Z += P[x];
			x = L[x];
		}else{
			Z += S[x];
			x = W[x];
		}
		if(x==N)return Z;
		for(int j = 29; j >=0; j--){
			if(wer2[x][j] < N){
				Z+=S[0]*(1<<j);
				x = wer2[x][j];
			}
		}
		if(Z < S[x]){
			Z += P[x];
			x = L[x];
		}else{
			Z += S[x];
			x = W[x];
		}
		if(x!=N)return 0;
	}
	return Z;
}

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