Submission #538816

#	Time	Username	Problem	Language	Result	Execution time	Memory
538816		MilosMilutinovic	Dungeons Game (IOI21_dungeons)	C++17	37 / 100	5337 ms	1679488 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=400050;
const int L=23;
const int K=9;
const ll inf=(ll)1e18;
int n,nxt[N][L][K],S[N],W[N];
ll pw[K+5],sum[N][L][K],mn[N][L][K],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[n][0][i]=n;
		sum[n][0][i]=0;
		mn[n][0][i]=inf;
		for(int j=0;j<n;j++){
			if(s[j]<=h){
				nxt[j][0][i]=w[j];
				sum[j][0][i]=s[j];
				mn[j][0][i]=inf;
			}else{
				nxt[j][0][i]=l[j];
				sum[j][0][i]=p[j];
				mn[j][0][i]=s[j];
			}
		}
		for(int j=1;j<L;j++)for(int l=0;l<=n;l++){
			nxt[l][j][i]=nxt[nxt[l][j-1][i]][j-1][i];
			sum[l][j][i]=min(inf,sum[l][j-1][i]+sum[nxt[l][j-1][i]][j-1][i]);
			mn[l][j][i]=min(mn[l][j-1][i],mn[nxt[l][j-1][i]][j-1][i]-sum[l][j-1][i]);
		}
	}
	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[x][j][i]>h){
					h+=sum[x][j][i];
					x=nxt[x][j][i];
				}
			}
			h+=S[x];x=W[x];
		}
	}
	return h+ft[x];
}

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