Submission #816532

#	Time	Username	Problem	Language	Result	Execution time	Memory
816532		penguinman	Dungeons Game (IOI21_dungeons)	C++17	37 / 100	7067 ms	139236 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;

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);
}

long long simulate(int x, int z) {
	ll now = x;
	ll ans = z;
	while(true){
		if(now == N-1) break;
		if(S[now] > ans){
			ans += P[now];
			now = L[now];
		}
		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: 0 / 13
• Subtask 4: 0 / 12
• Subtask 5: 0 / 27
• Subtask 6: 0 / 11