Submission #437869

#	Time	Username	Problem	Language	Result	Execution time	Memory
437869		b00n0rp	Dungeons Game (IOI21_dungeons)	C++17	63 / 100	2726 ms	1048580 KiB

dungeons

#include "dungeons.h"
#include<bits/stdc++.h>
using namespace std;
 
#define int long long
 
#define REP(i,n) for(int i = 0; i < n; i ++)
#define FOR(i,a,b) for(int i = a; i < b; i ++)
#define vi vector<int>
#define pb push_back
#define pii pair<int,int>
#define F first
#define S second
 
const int MX = 400005;
const int LG = 25;
const int STA = 5;
 
int n,s[MX],p[MX],w[MX],l[MX];
pii win[MX][LG+5];
int wincond[MX][LG+1];
pii lose[STA+1][MX][LG+1]; 
int losecond[STA+1][MX][LG+1];
vi st;
 
void init(signed n0, vector<signed> s0, vector<signed> p0, vector<signed> w0, vector<signed> l0) {
	n = n0;
	REP(i,n){
		s[i] = s0[i];
		p[i] = p0[i];
		w[i] = w0[i];
		l[i] = l0[i];
	}
	st.pb(4);
	FOR(i,1,STA) st.pb(4*st.back());
	w[n] = n;
	l[n] = n;
	s[n] = 0;
	p[n] = 0;
	REP(i,n+1){
		win[i][0] = {w[i],s[i]};
		wincond[i][0] = s[w[i]]-s[i];
	}
	FOR(j,1,LG+1){
		REP(i,n+1){
			win[i][j] = {win[win[i][j-1].F][j-1].F,win[win[i][j-1].F][j-1].S+win[i][j-1].S};
			wincond[i][j] = max(wincond[i][j-1],wincond[win[i][j-1].F][j-1]-win[i][j-1].S);
		}
	}
	REP(stage,STA+1){
		REP(i,n){
			if(stage and s[i] <= st[stage-1]){
				l[i] = w[i];
				p[i] = s[i];
				s[i] = (int)1e16;
			}
		}
		REP(i,n+1){
			lose[stage][i][0] = {l[i],p[i]};
			losecond[stage][i][0] = s[l[i]]-p[i];
			// int j = 0;
			// cout << stage << " " << i << " " << j << " " << losecond[stage][i][j] << " " << lose[stage][i][j].F << " " << lose[stage][i][j].S << "\n";
		}
		FOR(j,1,LG+1){
			REP(i,n+1){
				lose[stage][i][j] = {lose[stage][lose[stage][i][j-1].F][j-1].F,lose[stage][lose[stage][i][j-1].F][j-1].S+lose[stage][i][j-1].S};
				losecond[stage][i][j] = min(losecond[stage][i][j-1],losecond[stage][lose[stage][i][j-1].F][j-1]-lose[stage][i][j-1].S);
				// cout << stage << " " << i << " " << j << " " << losecond[stage][i][j] << " " << lose[stage][i][j].F << " " << lose[stage][i][j].S << "\n";
			}
		}
		REP(i,n){
			s[i] = s0[i];
			p[i] = p0[i];
			w[i] = w0[i];
			l[i] = l0[i];
		}
	}
}
 
int simulate(signed x, signed z) {
	int ind = x;
	int ans = z;
	int stage = 0;
	while(ind != n){
		// cout << ind << " " << ans << "\n";
		if(s[ind] > ans){
			while(stage < STA and st[stage] <= ans) stage++;
			for(int j = LG; j >= 0; j --){
				if(losecond[stage][ind][j] > ans){
					ans += lose[stage][ind][j].S;
					ind = lose[stage][ind][j].F;
				}
			}
			if(s[ind] > ans){
				ans += p[ind];
				ind = l[ind];
			}
		}
		else{
			for(int j = LG; j >= 0; j --){
				if(wincond[ind][j] <= ans){
					ans += win[ind][j].S;
					ind = win[ind][j].F;
				}
			}
			ans += s[ind];
			ind = w[ind];
		}
	}
	return ans;
}

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