Submission #538821

#	Time	Username	Problem	Language	Result	Execution time	Memory
538821		MilosMilutinovic	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	3613 ms	1555496 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=400050;
const int L=24;
const int K=8;
const ll inf=(ll)1e18;
int n,nxt[K][L][N],S[N],W[N];
ll pw[K+5],sum[K][L][N],mn[K][L][N],ft[N];
vector<pair<int,int>> E[N];
void DFS(int u,ll tot){
	ft[u]=tot;
	for(auto e:E[u])DFS(e.first,tot+e.second);
}
void init(int n,vector<int> s,vector<int> p,vector<int> w,vector<int> l){
	::n=n;for(int i=0;i<n;i++)S[i]=s[i],W[i]=w[i];W[n]=n;S[n]=0;
	pw[0]=1;for(int i=1;i<=K;i++)pw[i]=pw[i-1]*8;
	for(int i=0;i<K;i++){
		int h=pw[i];
		nxt[i][0][n]=n;
		sum[i][0][n]=0;
		mn[i][0][n]=inf;
		for(int j=0;j<n;j++){
			if(s[j]<=h){
				nxt[i][0][j]=w[j];
				sum[i][0][j]=s[j];
				mn[i][0][j]=inf;
			}else{
				nxt[i][0][j]=l[j];
				sum[i][0][j]=p[j];
				mn[i][0][j]=s[j];
			}
		}
		for(int j=1;j<L;j++)for(int l=0;l<=n;l++){
			nxt[i][j][l]=nxt[i][j-1][nxt[i][j-1][l]];
			sum[i][j][l]=min(inf,sum[i][j-1][l]+sum[i][j-1][nxt[i][j-1][l]]);
			mn[i][j][l]=min(mn[i][j-1][l],mn[i][j-1][nxt[i][j-1][l]]-sum[i][j-1][l]);
		}
	}
	for(int i=0;i<n;i++)E[w[i]].push_back({i,s[i]});
	DFS(n,0);
}
ll simulate(int x,int z){
	ll h=z;
	for(int i=0;i<K;i++){
		while(1){
			if(h>=pw[i+1]||x==n)break;
			for(int j=L-1;j>=0;j--){
				if(mn[i][j][x]>h){
					h+=sum[i][j][x];
					x=nxt[i][j][x];
				}
			}
			h+=S[x];x=W[x];
		}
	}
	return h+ft[x];
}

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