Submission #440538

#	Time	Username	Problem	Language	Result	Execution time	Memory
440538		mosiashvililuka	Dungeons Game (IOI21_dungeons)	C++17	37 / 100	7041 ms	278832 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,S[400009],P[400009],W[400009],L[400009],msh[400009][26],dis[400009][26],mn[400009][26],z;
void init(int Nn, std::vector<int> Ss, std::vector<int> Pp, std::vector<int> Ww, std::vector<int> Ll) {
	a=Nn;
	for(i=1; i<=a; i++){
		S[i]=Ss[i-1];P[i]=Pp[i-1];
		W[i]=Ww[i-1]+1;L[i]=Ll[i-1]+1;
	}
	for(i=1; i<=a; i++){
		msh[i][0]=W[i];dis[i][0]=S[i];mn[i][0]=-S[i];
	}
	for(j=1; j<=24; j++){
		for(i=1; i<=a; i++){
			msh[i][j]=msh[msh[i][j-1]][j-1];
			dis[i][j]=dis[i][j-1]+dis[msh[i][j-1]][j-1];
			mn[i][j]=min(mn[i][j-1],mn[msh[i][j-1]][j-1]+dis[i][j-1]);
		}
	}
	return;
}

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

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