oj.uz

Submission #817015

# Submission time Handle Problem Language Result Execution time Memory
817015 2023-08-09T08:30:42 Z penguinman Dungeons Game (IOI21_dungeons) C++17
50 / 100
 7000 ms 453600 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 3 ms 2260 KB Output is correct
4 Correct 104 ms 51076 KB Output is correct
5 Correct 3 ms 2260 KB Output is correct
6 Correct 113 ms 50816 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1256 KB Output is correct
2 Correct 850 ms 432536 KB Output is correct
3 Correct 814 ms 453600 KB Output is correct
4 Correct 790 ms 453460 KB Output is correct
5 Correct 992 ms 400104 KB Output is correct
6 Correct 873 ms 432920 KB Output is correct
7 Correct 752 ms 453388 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1236 KB Output is correct
2 Correct 116 ms 52388 KB Output is correct
3 Correct 115 ms 56608 KB Output is correct
4 Correct 103 ms 58604 KB Output is correct
5 Correct 116 ms 55880 KB Output is correct
6 Correct 123 ms 52084 KB Output is correct
7 Correct 127 ms 52072 KB Output is correct
8 Correct 103 ms 58368 KB Output is correct
9 Correct 108 ms 51772 KB Output is correct
10 Correct 106 ms 58264 KB Output is correct
11 Correct 154 ms 52156 KB Output is correct
12 Correct 251 ms 52244 KB Output is correct
13 Correct 222 ms 51016 KB Output is correct

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1236 KB Output is correct
2 Correct 116 ms 52388 KB Output is correct
3 Correct 115 ms 56608 KB Output is correct
4 Correct 103 ms 58604 KB Output is correct
5 Correct 116 ms 55880 KB Output is correct
6 Correct 123 ms 52084 KB Output is correct
7 Correct 127 ms 52072 KB Output is correct
8 Correct 103 ms 58368 KB Output is correct
9 Correct 108 ms 51772 KB Output is correct
10 Correct 106 ms 58264 KB Output is correct
11 Correct 154 ms 52156 KB Output is correct
12 Correct 251 ms 52244 KB Output is correct
13 Correct 222 ms 51016 KB Output is correct
14 Correct 2 ms 1236 KB Output is correct
15 Correct 173 ms 52216 KB Output is correct
16 Correct 118 ms 52436 KB Output is correct
17 Correct 112 ms 55104 KB Output is correct
18 Correct 112 ms 54976 KB Output is correct
19 Correct 167 ms 52088 KB Output is correct
20 Correct 120 ms 55752 KB Output is correct
21 Correct 116 ms 56004 KB Output is correct
22 Execution timed out 7067 ms 53860 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1236 KB Output is correct
2 Correct 116 ms 52388 KB Output is correct
3 Correct 115 ms 56608 KB Output is correct
4 Correct 103 ms 58604 KB Output is correct
5 Correct 116 ms 55880 KB Output is correct
6 Correct 123 ms 52084 KB Output is correct
7 Correct 127 ms 52072 KB Output is correct
8 Correct 103 ms 58368 KB Output is correct
9 Correct 108 ms 51772 KB Output is correct
10 Correct 106 ms 58264 KB Output is correct
11 Correct 154 ms 52156 KB Output is correct
12 Correct 251 ms 52244 KB Output is correct
13 Correct 222 ms 51016 KB Output is correct
14 Correct 2 ms 1236 KB Output is correct
15 Correct 173 ms 52216 KB Output is correct
16 Correct 118 ms 52436 KB Output is correct
17 Correct 112 ms 55104 KB Output is correct
18 Correct 112 ms 54976 KB Output is correct
19 Correct 167 ms 52088 KB Output is correct
20 Correct 120 ms 55752 KB Output is correct
21 Correct 116 ms 56004 KB Output is correct
22 Execution timed out 7067 ms 53860 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1256 KB Output is correct
2 Correct 850 ms 432536 KB Output is correct
3 Correct 814 ms 453600 KB Output is correct
4 Correct 790 ms 453460 KB Output is correct
5 Correct 992 ms 400104 KB Output is correct
6 Correct 873 ms 432920 KB Output is correct
7 Correct 752 ms 453388 KB Output is correct
8 Correct 2 ms 1236 KB Output is correct
9 Correct 116 ms 52388 KB Output is correct
10 Correct 115 ms 56608 KB Output is correct
11 Correct 103 ms 58604 KB Output is correct
12 Correct 116 ms 55880 KB Output is correct
13 Correct 123 ms 52084 KB Output is correct
14 Correct 127 ms 52072 KB Output is correct
15 Correct 103 ms 58368 KB Output is correct
16 Correct 108 ms 51772 KB Output is correct
17 Correct 106 ms 58264 KB Output is correct
18 Correct 154 ms 52156 KB Output is correct
19 Correct 251 ms 52244 KB Output is correct
20 Correct 222 ms 51016 KB Output is correct
21 Correct 2 ms 1236 KB Output is correct
22 Correct 173 ms 52216 KB Output is correct
23 Correct 118 ms 52436 KB Output is correct
24 Correct 112 ms 55104 KB Output is correct
25 Correct 112 ms 54976 KB Output is correct
26 Correct 167 ms 52088 KB Output is correct
27 Correct 120 ms 55752 KB Output is correct
28 Correct 116 ms 56004 KB Output is correct
29 Execution timed out 7067 ms 53860 KB Time limit exceeded
30 Halted 0 ms 0 KB -