oj.uz

Submission #817948

# Submission time Handle Problem Language Result Execution time Memory
817948 2023-08-09T21:18:46 Z FEDIKUS Dungeons Game (IOI21_dungeons) C++17
100 / 100
 4279 ms 1443804 KB 
#include<bits/stdc++.h>
#include "dungeons.h"

using namespace std;

typedef long long ll;

const int logz=12;
const int logn=25;
const int maxn=8*50000+10;
const int inf=1e7+10;

struct{
	int gain,max;
	int pos;
} lift[logz][logn][maxn];

ll dokraja[maxn];
int n;
vector<int> s,p;
vector<int> w,l;

void init(int nn, vector<int> ss, vector<int> pp, vector<int> ww, vector<int> ll) {
	n=nn; s=ss; p=pp; w=ww; l=ll;
	s.resize(n+1); p.resize(n+1); w.resize(n+1), l.resize(n+1);
	s[n]=0; p[n]=0; w[n]=n; l[n]=n;
	for(int bit=0;bit<logz;bit++){
		for(int jump=0;jump<logn;jump++){
			for(int pos=0;pos<=n;pos++){
				if(jump==0){
					if((1<<bit*2)>=s[pos]) lift[bit][jump][pos]={s[pos],INT_MIN,w[pos]};
					else lift[bit][jump][pos]={p[pos],-s[pos],l[pos]};
				}else{
					lift[bit][jump][pos]={lift[bit][jump-1][pos].gain+lift[bit][jump-1][lift[bit][jump-1][pos].pos].gain,
									      max(lift[bit][jump-1][pos].max,lift[bit][jump-1][pos].gain+lift[bit][jump-1][lift[bit][jump-1][pos].pos].max),
										  lift[bit][jump-1][lift[bit][jump-1][pos].pos].pos};
					if(lift[bit][jump][pos].gain>inf){
						lift[bit][jump][pos].gain=inf;
						lift[bit][jump][pos].max=1;
					}
				}
			}
		}
	}
	for(int i=n;i>=0;i--){
		dokraja[i]=dokraja[w[i]]+s[i];
	}
	return;
}

int get_bit(ll a){
	return min(63-__builtin_clzll(a),logz-1)/2;
}

long long simulate(int x, int z) {
	long long res=z;
	int klk=0;
	while(true){
		klk++;
		if(res==0){
			res=p[x];
			x=l[x];
			continue;
		}
		int bit=get_bit(res);
		for(int jump=logn-1;jump>=0;jump--){
			if(res+lift[bit][jump][x].max<0){
				res+=lift[bit][jump][x].gain;
				x=lift[bit][jump][x].pos;
			}
		}
		if((1LL<<2*bit)<s[x] && res>=s[x]){
			res+=s[x];
			x=w[x];
		}
		if(res>inf){
			res+=dokraja[x];
			break;	
		}
		if(x==n) break;
	}
	return res;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 5 ms 9812 KB Output is correct
4 Correct 111 ms 181548 KB Output is correct
5 Correct 6 ms 9812 KB Output is correct
6 Correct 110 ms 181548 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6228 KB Output is correct
2 Correct 1131 ms 1432060 KB Output is correct
3 Correct 913 ms 1432012 KB Output is correct
4 Correct 963 ms 1432108 KB Output is correct
5 Correct 958 ms 1432260 KB Output is correct
6 Correct 966 ms 1432152 KB Output is correct
7 Correct 996 ms 1432096 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6344 KB Output is correct
2 Correct 179 ms 183976 KB Output is correct
3 Correct 159 ms 184108 KB Output is correct
4 Correct 139 ms 183488 KB Output is correct
5 Correct 144 ms 183408 KB Output is correct
6 Correct 187 ms 183624 KB Output is correct
7 Correct 171 ms 183624 KB Output is correct
8 Correct 153 ms 183352 KB Output is correct
9 Correct 147 ms 183268 KB Output is correct
10 Correct 136 ms 183228 KB Output is correct
11 Correct 147 ms 183508 KB Output is correct
12 Correct 221 ms 183680 KB Output is correct
13 Correct 198 ms 183552 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6344 KB Output is correct
2 Correct 179 ms 183976 KB Output is correct
3 Correct 159 ms 184108 KB Output is correct
4 Correct 139 ms 183488 KB Output is correct
5 Correct 144 ms 183408 KB Output is correct
6 Correct 187 ms 183624 KB Output is correct
7 Correct 171 ms 183624 KB Output is correct
8 Correct 153 ms 183352 KB Output is correct
9 Correct 147 ms 183268 KB Output is correct
10 Correct 136 ms 183228 KB Output is correct
11 Correct 147 ms 183508 KB Output is correct
12 Correct 221 ms 183680 KB Output is correct
13 Correct 198 ms 183552 KB Output is correct
14 Correct 4 ms 6356 KB Output is correct
15 Correct 155 ms 183848 KB Output is correct
16 Correct 176 ms 184072 KB Output is correct
17 Correct 144 ms 183468 KB Output is correct
18 Correct 137 ms 183488 KB Output is correct
19 Correct 180 ms 183624 KB Output is correct
20 Correct 182 ms 183316 KB Output is correct
21 Correct 161 ms 183392 KB Output is correct
22 Correct 151 ms 183508 KB Output is correct
23 Correct 168 ms 183616 KB Output is correct
24 Correct 255 ms 183596 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6344 KB Output is correct
2 Correct 179 ms 183976 KB Output is correct
3 Correct 159 ms 184108 KB Output is correct
4 Correct 139 ms 183488 KB Output is correct
5 Correct 144 ms 183408 KB Output is correct
6 Correct 187 ms 183624 KB Output is correct
7 Correct 171 ms 183624 KB Output is correct
8 Correct 153 ms 183352 KB Output is correct
9 Correct 147 ms 183268 KB Output is correct
10 Correct 136 ms 183228 KB Output is correct
11 Correct 147 ms 183508 KB Output is correct
12 Correct 221 ms 183680 KB Output is correct
13 Correct 198 ms 183552 KB Output is correct
14 Correct 4 ms 6356 KB Output is correct
15 Correct 155 ms 183848 KB Output is correct
16 Correct 176 ms 184072 KB Output is correct
17 Correct 144 ms 183468 KB Output is correct
18 Correct 137 ms 183488 KB Output is correct
19 Correct 180 ms 183624 KB Output is correct
20 Correct 182 ms 183316 KB Output is correct
21 Correct 161 ms 183392 KB Output is correct
22 Correct 151 ms 183508 KB Output is correct
23 Correct 168 ms 183616 KB Output is correct
24 Correct 255 ms 183596 KB Output is correct
25 Correct 127 ms 182832 KB Output is correct
26 Correct 165 ms 183980 KB Output is correct
27 Correct 168 ms 183368 KB Output is correct
28 Correct 156 ms 183492 KB Output is correct
29 Correct 177 ms 183868 KB Output is correct
30 Correct 191 ms 183800 KB Output is correct
31 Correct 204 ms 183320 KB Output is correct
32 Correct 270 ms 183484 KB Output is correct
33 Correct 549 ms 183464 KB Output is correct
34 Correct 928 ms 183344 KB Output is correct
35 Correct 1577 ms 183484 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6228 KB Output is correct
2 Correct 1131 ms 1432060 KB Output is correct
3 Correct 913 ms 1432012 KB Output is correct
4 Correct 963 ms 1432108 KB Output is correct
5 Correct 958 ms 1432260 KB Output is correct
6 Correct 966 ms 1432152 KB Output is correct
7 Correct 996 ms 1432096 KB Output is correct
8 Correct 4 ms 6344 KB Output is correct
9 Correct 179 ms 183976 KB Output is correct
10 Correct 159 ms 184108 KB Output is correct
11 Correct 139 ms 183488 KB Output is correct
12 Correct 144 ms 183408 KB Output is correct
13 Correct 187 ms 183624 KB Output is correct
14 Correct 171 ms 183624 KB Output is correct
15 Correct 153 ms 183352 KB Output is correct
16 Correct 147 ms 183268 KB Output is correct
17 Correct 136 ms 183228 KB Output is correct
18 Correct 147 ms 183508 KB Output is correct
19 Correct 221 ms 183680 KB Output is correct
20 Correct 198 ms 183552 KB Output is correct
21 Correct 4 ms 6356 KB Output is correct
22 Correct 155 ms 183848 KB Output is correct
23 Correct 176 ms 184072 KB Output is correct
24 Correct 144 ms 183468 KB Output is correct
25 Correct 137 ms 183488 KB Output is correct
26 Correct 180 ms 183624 KB Output is correct
27 Correct 182 ms 183316 KB Output is correct
28 Correct 161 ms 183392 KB Output is correct
29 Correct 151 ms 183508 KB Output is correct
30 Correct 168 ms 183616 KB Output is correct
31 Correct 255 ms 183596 KB Output is correct
32 Correct 127 ms 182832 KB Output is correct
33 Correct 165 ms 183980 KB Output is correct
34 Correct 168 ms 183368 KB Output is correct
35 Correct 156 ms 183492 KB Output is correct
36 Correct 177 ms 183868 KB Output is correct
37 Correct 191 ms 183800 KB Output is correct
38 Correct 204 ms 183320 KB Output is correct
39 Correct 270 ms 183484 KB Output is correct
40 Correct 549 ms 183464 KB Output is correct
41 Correct 928 ms 183344 KB Output is correct
42 Correct 1577 ms 183484 KB Output is correct
43 Correct 1 ms 2644 KB Output is correct
44 Correct 4 ms 6356 KB Output is correct
45 Correct 1179 ms 1443680 KB Output is correct
46 Correct 1008 ms 1439048 KB Output is correct
47 Correct 918 ms 1439376 KB Output is correct
48 Correct 905 ms 1441552 KB Output is correct
49 Correct 1162 ms 1443804 KB Output is correct
50 Correct 921 ms 1441256 KB Output is correct
51 Correct 890 ms 1441696 KB Output is correct
52 Correct 915 ms 1439320 KB Output is correct
53 Correct 1518 ms 1440068 KB Output is correct
54 Correct 1704 ms 1441160 KB Output is correct
55 Correct 2153 ms 1440136 KB Output is correct
56 Correct 4279 ms 1440872 KB Output is correct
57 Correct 3346 ms 1440988 KB Output is correct
58 Correct 2929 ms 1440928 KB Output is correct
59 Correct 2416 ms 1441104 KB Output is correct
60 Correct 3018 ms 1440248 KB Output is correct
61 Correct 2901 ms 1440288 KB Output is correct