Submission #602590

#	Time	Username	Problem	Language	Result	Execution time	Memory
602590		rrrr10000	Dungeons Game (IOI21_dungeons)	C++17	37 / 100	7063 ms	231948 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> P;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef tuple<ll,ll,ll> PP;
typedef vector<PP> vpp;
typedef vector<vpp> vvpp;
#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 pb emplace_back
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}

ll n;
vi s,p,w,l;
vvpp table;
PP f(PP a,PP b){
	chmax(get<1>(a),get<1>(b)-get<2>(a));
	get<2>(a)+=get<2>(b);
	get<0>(a)=get<0>(b);
	return a;
}
void init(int n_, vector<int> s_, vector<int> p_, vector<int> w_, vector<int> l_){
	n=n_+1;
	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);
	s.pb(0);p.pb(0);w.pb(n-1);l.pb(n-1);
	table=vvpp(20,vpp(n));
	rep(i,n)table[0][i]=PP(w[i],s[i],s[i]);
	rep(i,19)rep(j,n)table[i+1][j]=f(table[i][j],table[i][get<0>(table[i][j])]);
	return;
}

long long simulate(int x_, int z_) {
	ll i=x_,cur=z_;
	/*
	while(i<n-1){
		if(cur>=s[i]){
			cur+=s[i];
			i=w[i];
		}
		else{
			cur+=p[i];
			i=l[i];
		}
	}
	*/
	while(i<n-1){
		if(cur<s[i]){
			cur+=p[i];i=l[i];
		}
		else{
			PP tmp(i,0,0);
			for(ll j=19;j>=0;j--){
				auto ntmp=f(tmp,table[j][get<0>(tmp)]);
				if(get<1>(ntmp)<=cur){
					tmp=ntmp;
				}
			}
			i=get<0>(tmp);cur+=get<2>(tmp);
		}
	}
	return cur;
}

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