Submission #619056

#	Time	Username	Problem	Language	Result	Execution time	Memory
619056		KLPP	Dungeons Game (IOI21_dungeons)	C++17	13 / 100	161 ms	30356 KiB

dungeons

#include "dungeons.h"
#include <vector>
#include<bits/stdc++.h>

using namespace std;
typedef long long int lld;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)

lld S[1000000];
lld P[1000000];
lld W[1000000];
lld L[1000000];
pair<int,lld> STL[1000000][32];
lld NW[1000000];
int N;
void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
	N=n;
	rep(i,0,n){
		S[i]=s[i];
		P[i]=p[i];
		W[i]=w[i];
		L[i]=l[i];
	}
	L[n]=n;
	P[n]=0;
	NW[n]=0;
	for(int i=n-1;i>-1;i--){
		NW[i]=NW[W[i]]+S[i];
	}
	rep(i,0,n+1){
		STL[i][0]={L[i],P[i]};
		STL[i][0].second=min(STL[i][0].second,S[i]);
	}
	for(int j=1;j<32;j++){
		rep(i,0,n+1){
			STL[i][j]={STL[STL[i][j-1].first][j-1].first,STL[STL[i][j-1].first][j-1].second+STL[i][j-1].second};
			STL[i][j].second=min(STL[i][j].second,S[i]);
		}
	}
}
#define DEBUG 0

lld Simulate(int x, lld z){
	if(x==N)return z;
	for(int j=31;j>-1;j--){
		if(STL[x][j].second+z<S[x]){
			z+=STL[x][j].second;
			x=STL[x][j].first;
			return Simulate(x,z);
		}
	}
	if(z<S[x]){
		return Simulate(L[x],z+P[x]);
	}else{
		return z+NW[x];
	}
}


long long simulate(int x, int z) {
	if(DEBUG){
		//cout<<x<<" "<<z<<endl;
		if(x==N)return z;
		if(z<S[x])return simulate(L[x],z+P[x]);
		return simulate(W[x],z+S[x]);
	}
	return Simulate(x,z);
}

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