Submission #835629

#	Time	Username	Problem	Language	Result	Execution time	Memory
835629		ttamx	Dungeons Game (IOI21_dungeons)	C++17	11 / 100	7077 ms	516704 KiB

dungeons

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

using namespace std;

typedef long long ll;

const int N=400005;
const int K=25;
const ll inf=1e18;
const int S=1e7;

int n;
int s[N],p[N],w[N],l[N];

struct edge{
	int to;
	ll add,lim;
	edge(){}
	edge(int to,ll add,ll lim):to(to),add(add),lim(lim){}
}dp[K][N][2];

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],p[i]=_p[i],w[i]=_w[i],l[i]=_l[i];
	s[n]=p[n]=0;
	w[n]=l[n]=n;
	for(int i=0;i<K;i++){
		for(int u=0;u<n;u++){
			if(s[u]<=(1<<i)){
				dp[i][u][0]=edge(w[u],s[u],inf);
			}else{
				dp[i][u][0]=edge(l[u],p[u],s[u]);
			}
		}
		dp[i][n][0]=dp[i][n][1]=edge(n,0,inf);
		vector<vector<int>> adj(n+1);
		vector<int> dep(n+1);
		for(int u=0;u<n;u++)adj[dp[i][u][0].to].emplace_back(u);
		queue<int> q;
		q.emplace(n);
		dep[n]=0;
		while(!q.empty()){
			auto u=q.front();
			q.pop();
			int jump=dp[i][u][1].to;
			int jump2=dp[i][jump][1].to;
			bool ok=dep[u]-dep[jump]==dep[jump]-dep[jump2];
			for(auto v:adj[u]){
				dep[v]=dep[u]+1;
				if(ok){
					auto e=dp[i][v][0];
					e=edge(e.to,e.add+dp[i][u][1].add,min(e.lim,dp[i][u][1].lim-e.add));
					dp[i][v][1]=edge(e.to,e.add+dp[i][jump][1].add,min(e.lim,dp[i][jump][1].lim-e.add));
				}else{
					dp[i][v][1]=dp[i][v][0];
				}
			}
		}
	}
}

ll simulate(int x, int z){
	int phase=0;
	ll sz=1;
	int cur=x;
	ll val=z;
	while(cur!=n){
		if(val<S){
			while(sz*2<=val){
				sz*=2;
				phase++;
			}
			while(cur!=n){
				auto e=dp[phase][cur][1];
				if(val>=e.lim)e=dp[phase][cur][0];
				if(val>=e.lim)break;
				val+=e.add;
				cur=e.to;
			}
		}
		if(val>=s[cur]){
			val+=s[cur];
			cur=w[cur];
		}else{
			val+=p[cur];
			cur=l[cur];
		}
	}
	return val;
}

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