Submission #1047083

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047083		Unforgettablepl	Dungeons Game (IOI21_dungeons)	C++17	25 / 100	180 ms	212416 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
 
const int INF = 1e8;
 
vector<int> s,p,w,l;
vector<vector<vector<int>>> lift;
vector<vector<vector<long long>>> liftcost;
vector<long long> bestans;
vector<int> phases;
int n,phasescnt;
 
void init(int n,vector<int> s,vector<int> p,vector<int> w,vector<int> l){
	::n=n;
	::s=s;
	::p=p;
	::w=w;
	::l=l;
	phases = s;
	sort(phases.begin(),phases.end());
	phases.erase(unique(phases.begin(),phases.end()),phases.end());
	phasescnt = phases.size();
	lift = vector(5,vector(n+1,vector(24,0)));
	liftcost = vector(5,vector(n+1,vector(24,0ll)));
	bestans = vector(n+1,0ll);
	for(int i=n-1;i>=0;i--){
		bestans[i]=bestans[w[i]]+s[i];
		for(int phase=0;phase<phasescnt;phase++){
			if(s[i]<phases[phase]){
				lift[phase][i][0]=w[i];
				liftcost[phase][i][0]=s[i];
			} else {
				lift[phase][i][0]=l[i];
				liftcost[phase][i][0]=p[i];
			}
		}
	}
	for(int phase=0;phase<phasescnt;phase++){
		liftcost[phase][n][0]=INF;
		lift[phase][n][0]=n;
	}
	for(int phase=0;phase<phasescnt;phase++){
		for(int bit=1;bit<24;bit++){
			for(int i=0;i<=n;i++){
				lift[phase][i][bit]=lift[phase][lift[phase][i][bit-1]][bit-1];
				liftcost[phase][i][bit]=liftcost[phase][i][bit-1]+liftcost[phase][lift[phase][i][bit-1]][bit-1];
			}
		}
	}
	return;
}
 
long long simulate(int x,int z){
	for(int phase=0;phase<phasescnt;phase++){
		for(int bit=23;bit>=0;bit--){
			if(z+liftcost[phase][x][bit]<phases[phase]){
				z+=liftcost[phase][x][bit];
				x=lift[phase][x][bit];
			}
		}
		if(x==n)return z;
		if(z<phases[phase]){
			z+= liftcost[phase][x][0];
			x = lift[phase][x][0];
		}
	}
	return z+bestans[x];
}

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