Submission #1046081

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046081		Unforgettablepl	Dungeons Game (IOI21_dungeons)	C++17	37 / 100	403 ms	254804 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;

const long long INF = 1e15;

vector<int> s,p,w,l;
vector<vector<int>> lift;
vector<vector<long long>> liftcost;
vector<vector<long long>> liftneed;
vector<long long> bestans;
int n;
bool special_case;

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;
	special_case = true;
	for(int i=1;i<n;i++)if(s[i]!=s[0])special_case=false;
	if(special_case){
		lift = vector(n+1,vector(24,0));
		liftcost = 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];
			lift[i][0] = l[i];
			liftcost[i][0] = p[i];
		}
		liftcost[n][0]=INF;
		lift[n][0]=n;
		for(int bit=1;bit<24;bit++){
			for(int i=0;i<=n;i++){
				lift[i][bit]=lift[lift[i][bit-1]][bit-1];
				liftcost[i][bit]=liftcost[i][bit-1]+liftcost[lift[i][bit-1]][bit-1];
			}
		}
		return;
	}
	lift = vector(n+1,vector(24,0));
	liftcost = vector(n+1,vector(24,0ll));
	liftneed = vector(n+1,vector(24,0ll));
	for(int i=0;i<n;i++){
		lift[i][0] = w[i];
		liftcost[i][0] = s[i];
		liftneed[i][0] = s[i];
	}
	liftcost[n][0]=INF;
	liftneed[n][0]=INF;
	lift[n][0]=n;
	for(int bit=1;bit<24;bit++){
		for(int i=0;i<=n;i++){
			lift[i][bit]=lift[lift[i][bit-1]][bit-1];
			liftcost[i][bit]=liftcost[i][bit-1]+liftcost[lift[i][bit-1]][bit-1];
			liftneed[i][bit]=max(liftneed[i][bit-1],liftneed[lift[i][bit-1]][bit-1]-liftcost[i][bit-1]);
		}
	}
	return;
}

long long simulate(int x,int z){
	if(special_case){
		for(int bit=23;bit>=0;bit--){
			if(z+liftcost[x][bit]<s[0]){
				z+=liftcost[x][bit];
				x=lift[x][bit];
			}
		}
		if(x==n)return z;
		if(z<s[0]){
			z+=liftcost[x][0];
			x = lift[x][0];
		}
		return z+bestans[x];
	}
	while(x!=n){		
		for(int bit=23;bit>=0;bit--){
			if(z>=liftneed[x][bit]){
				z+=liftcost[x][bit];
				x=lift[x][bit];
			}
		}
		if(x==n)return z;
		z += p[x];
		x = l[x];
	}
	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