Submission #817015

#	Time	Username	Problem	Language	Result	Execution time	Memory
817015		penguinman	Dungeons Game (IOI21_dungeons)	C++17	50 / 100	7067 ms	453600 KiB

dungeons

#include "dungeons.h"

#include <bits/stdc++.h>

using std::cin;
using std::cout;
using std::vector;
using std::string;
using std::endl;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;

#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define ln "\n"
#define all(a) a.begin(), a.end()
#define pb emplace_back
#define mp std::make_pair

constexpr ll inf = (1ll<<60);

struct segment_tree{
	ll N;
	vi node;
	segment_tree(int n){
		N = 1;
		while(N <= n) N *= 2;
		node.resize(2*N,-inf);
	}
	void update(ll idx, ll val){
		idx += N;
		node[idx] = val;
		idx /= 2;
		while(idx){
			node[idx] = compare(node[idx*2], node[idx*2+1]);
			idx /= 2;
		}
	}
	ll min_right(ll val, ll a, ll now = 1, ll l = 0, ll r = -1){
		if(r == -1) r = N;
		if(r <= a) return r;
		if(val >= node[now]) return r;
		if(now >= N) return l;
		ll mid = min_right(val, a, now*2, l, (l+r)/2);
		if(mid == (l+r)/2) return min_right(val, a, now*2+1, (l+r)/2, r);
		return mid;
	}
	ll compare(ll l, ll r){
		return std::max(l,r);
	}
};

vii t1_edge, t1_weight;
vi t1_dist, t1_par, t1_next;
ll N;
vi S,P,W,L;
vii min, sum, idx;
constexpr ll LOG = 30;

void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
	N = n+1;
	rep(i,0,n) S.pb(s[i]), P.pb(p[i]), W.pb(w[i]), L.pb(l[i]);
	{
		t1_edge.resize(N);
		t1_weight.resize(N);
		t1_dist.resize(N);
		t1_par.resize(N);
		t1_next.resize(N);
		rep(i,0,n){
			t1_edge[w[i]].pb(i);
			t1_weight[w[i]].pb(s[i]);
			t1_par[i] = w[i];
		}
		vi dist2(N);
		segment_tree seg(N+1);
		vi v;
		std::function<void(ll)> dfs = [&](ll now){
			v.pb(now);
			t1_next[now] = v[std::max(0ll, N-seg.min_right(s[now]+t1_dist[now], 0))];
			seg.update(N-dist2[now], s[now]+t1_dist[now]);
			for(auto next: t1_edge[now]){
				dist2[next] = dist2[now]+1;
				t1_dist[next] = t1_dist[now]+s[next];
				dfs(next);
			}
			seg.update(N-dist2[now], -inf);
			v.pop_back();
		};
		dfs(N-1);
	}
	{
		min.resize(N,vi(LOG,-inf));
		sum.resize(N,vi(LOG));
		idx.resize(N,vi(LOG));
		L.pb(N-1);
		P.pb(0);
		S.pb(-inf);
		rep(i,0,N){
			idx[i][0] = L[i];
			sum[i][0] = P[i];
			min[i][0] = S[i];
		}
		rep(j,1,LOG){
			rep(i,0,N){
				ll now = idx[i][j-1];
				ll next = idx[now][j-1];
				idx[i][j] = next;
				sum[i][j] = sum[i][j-1]+sum[now][j-1];
				min[i][j] = std::min(min[i][j-1], min[now][j-1]-sum[i][j-1]);
			}
		}
	}
}

long long simulate(int x, int z) {
	ll now = x;
	ll ans = z;
	while(true){
		if(now == N-1) break;
		if(S[now] > ans){
			per(i,LOG-1,0){
				if(min[now][i] > ans){
					ans += sum[now][i];
					now = idx[now][i];
				}
			}
		}
		else{
			ans += t1_dist[now]-t1_dist[t1_next[now]];
			now = t1_next[now];
		}
	}
	return ans;
}

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