Submission #815911

#	Time	Username	Problem	Language	Result	Execution time	Memory
815911		blackyuki	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	4588 ms	261272 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<bool> vb;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define all(a) a.begin(),a.end()
#define fi first
#define se second
#define pb emplace_back
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
const ll inf=1001001001001001001;

ll mx=10000005,B=2000,lg=24,n;
vi s,p,w,l,dp;
vector<vector<PP>> table;
void init(int n_, std::vector<int> s_, std::vector<int> p_, std::vector<int> w_, std::vector<int> l_) {
	n=n_;
	for(ll x:s_)s.pb(x);
	for(ll x:p_)p.pb(x);
	for(ll x:w_)w.pb(x);
	for(ll x:l_)l.pb(x);
	table=vector<vector<PP>>(lg,vector<PP>(n,PP(n,-1,-1)));
	rep(i,n){
		if(s[i]>B)table[0][i]=PP(l[i],p[i],s[i]);
		else table[0][i]=PP(w[i],s[i],inf);
	}
	rep(i,lg-1)rep(j,n)if(get<0>(table[i][j])!=n){
		get<0>(table[i+1][j])=get<0>(table[i][get<0>(table[i][j])]);
		get<1>(table[i+1][j])=get<1>(table[i][j])+get<1>(table[i][get<0>(table[i][j])]);
		get<2>(table[i+1][j])=min(get<2>(table[i][j]),get<2>(table[i][get<0>(table[i][j])])-get<1>(table[i][j]));
	}
	dp=vi(n+1);
	for(ll i=n-1;i>=0;i--)dp[i]=dp[w[i]]+s[i];
}

long long simulate(int x, int z) {
	ll curx=x,curz=z;
	while(curx<n&&curz<B){
		if(s[curx]<=curz){
			curz+=s[curx];curx=w[curx];
		}
		else{
			curz+=p[curx];curx=l[curx];
		}
	}
	if(curx==n)return curz;
	while(curx<n&&curz<mx){
		for(ll i=lg-1;i>=0;i--)if(get<0>(table[i][curx])<n&&curz<get<2>(table[i][curx])){
			curz+=get<1>(table[i][curx]);
			curx=get<0>(table[i][curx]);
		}
		if(s[curx]<=curz){
			curz+=s[curx];curx=w[curx];
		}
		else{
			curz+=p[curx];curx=l[curx];
		}
	}
	return dp[curx]+curz;
}

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