Submission #448349

#	Time	Username	Problem	Language	Result	Execution time	Memory
448349		mosiashvililuka	Dungeons Game (IOI21_dungeons)	C++17	63 / 100	2224 ms	991432 KiB

dungeons

#include<bits/stdc++.h>
#include "dungeons.h"
using namespace std;
const int N=50009;
int msh[N][26][26];
long long a,b,c,d,e,i,j,k,ii,jj,zx,xc,S[N],P[N],W[N],L[N],dis[N][26][26],mn[N][26][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=0; i<a; i++){
		S[i+1]=Ss[i];P[i+1]=Pp[i];W[i+1]=Ww[i]+1;L[i+1]=Ll[i]+1;
	}
	for(i=1; i<=a; i++){
		for(k=0; k<=24; k++){
			if(S[i]<(1<<k)){
				msh[i][0][k]=W[i];
				dis[i][0][k]=S[i];
				mn[i][0][k]=99999999999999999LL;
			}else{
				msh[i][0][k]=L[i];
				dis[i][0][k]=P[i];
				mn[i][0][k]=S[i];
			}
		}
	}
	for(j=1; j<=24; j++){
		for(i=1; i<=a; i++){
			for(k=0; k<=24; k++){
				msh[i][j][k]=msh[msh[i][j-1][k]][j-1][k];
				dis[i][j][k]=dis[i][j-1][k]+dis[msh[i][j-1][k]][j-1][k];
				mn[i][j][k]=min(mn[i][j-1][k],mn[msh[i][j-1][k]][j-1][k]-dis[i][j-1][k]);
			}
		}
	}
	return;
}

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