#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mxn = 4e5+1;
const int m = 25;
const int c = 5;
ll b[mxn][m][c], t[mxn][m][c], a[mxn][m][c], suf[mxn];
vector<int> s, p, w, l;
int n;
const ll inf = (1ll<<60);
void init(int _n, vector<int> _s, vector<int> _p, vector<int> _w, vector<int> _l) {
n = _n, s = _s, p = _p, w = _w, l = _l;
suf[n] = 0;
for(int i = n-1; ~i; --i){
suf[i] = s[i] + suf[w[i]];
}
for(int i = 0; i < c; ++i){
b[n][0][i] = n;
t[n][0][i] = inf;
a[n][0][i] = 0;
for(int k = 0; k < n; ++k){
if(s[k] <= (1<<(i*5))){
t[k][0][i] = inf;
a[k][0][i] = s[k];
b[k][0][i] = w[k];
}
else{
t[k][0][i] = s[k];
a[k][0][i] = p[k];
b[k][0][i] = l[k];
}
}
for(int j = 1; j < m; ++j){
for(int k = 0; k < n; ++k){
int cur = j-1;
t[k][j][i] = (t[b[k][cur][i]][cur][i] == inf ? t[k][cur][i] : min(t[b[k][cur][i]][cur][i] - a[k][cur][i], t[k][cur][i]));
a[k][j][i] = a[b[k][cur][i]][cur][i] + a[k][cur][i];
b[k][j][i] = b[b[k][cur][i]][cur][i];
}
}
}
}
ll simulate(int x, int _z) {
ll z = _z;
for(int i = 0; i < c; ++i){
for(int _ = 0; _ < (1<<5); ++_){
for(int j = m-1; ~j; --j){
if(z < t[x][j][i]){
z += a[x][j][i];
x = b[x][j][i];
}
}
if(x == n)break;
if(z >= s[x]){
z += s[x];
x = w[x];
} else {
z += p[x];
x = l[x];
}
}
}
z+=suf[x];
return z;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
6 ms |
6228 KB |
Output is correct |
4 |
Correct |
293 ms |
149852 KB |
Output is correct |
5 |
Correct |
5 ms |
6228 KB |
Output is correct |
6 |
Correct |
321 ms |
149852 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
3292 KB |
Output is correct |
2 |
Correct |
2998 ms |
1197192 KB |
Output is correct |
3 |
Correct |
2972 ms |
1197180 KB |
Output is correct |
4 |
Correct |
2949 ms |
1197184 KB |
Output is correct |
5 |
Correct |
2480 ms |
1197240 KB |
Output is correct |
6 |
Correct |
2913 ms |
1197184 KB |
Output is correct |
7 |
Correct |
3376 ms |
1197184 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
3284 KB |
Output is correct |
2 |
Correct |
386 ms |
150620 KB |
Output is correct |
3 |
Correct |
1333 ms |
150636 KB |
Output is correct |
4 |
Correct |
566 ms |
150616 KB |
Output is correct |
5 |
Correct |
579 ms |
150732 KB |
Output is correct |
6 |
Correct |
372 ms |
150640 KB |
Output is correct |
7 |
Correct |
362 ms |
150664 KB |
Output is correct |
8 |
Correct |
557 ms |
150636 KB |
Output is correct |
9 |
Correct |
362 ms |
150636 KB |
Output is correct |
10 |
Correct |
571 ms |
150628 KB |
Output is correct |
11 |
Correct |
425 ms |
150640 KB |
Output is correct |
12 |
Correct |
885 ms |
150636 KB |
Output is correct |
13 |
Correct |
435 ms |
150636 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
3284 KB |
Output is correct |
2 |
Correct |
386 ms |
150620 KB |
Output is correct |
3 |
Correct |
1333 ms |
150636 KB |
Output is correct |
4 |
Correct |
566 ms |
150616 KB |
Output is correct |
5 |
Correct |
579 ms |
150732 KB |
Output is correct |
6 |
Correct |
372 ms |
150640 KB |
Output is correct |
7 |
Correct |
362 ms |
150664 KB |
Output is correct |
8 |
Correct |
557 ms |
150636 KB |
Output is correct |
9 |
Correct |
362 ms |
150636 KB |
Output is correct |
10 |
Correct |
571 ms |
150628 KB |
Output is correct |
11 |
Correct |
425 ms |
150640 KB |
Output is correct |
12 |
Correct |
885 ms |
150636 KB |
Output is correct |
13 |
Correct |
435 ms |
150636 KB |
Output is correct |
14 |
Correct |
5 ms |
3284 KB |
Output is correct |
15 |
Correct |
447 ms |
150628 KB |
Output is correct |
16 |
Correct |
381 ms |
150636 KB |
Output is correct |
17 |
Correct |
796 ms |
150628 KB |
Output is correct |
18 |
Correct |
794 ms |
150604 KB |
Output is correct |
19 |
Correct |
384 ms |
150628 KB |
Output is correct |
20 |
Correct |
774 ms |
150628 KB |
Output is correct |
21 |
Correct |
690 ms |
150636 KB |
Output is correct |
22 |
Correct |
759 ms |
150628 KB |
Output is correct |
23 |
Correct |
478 ms |
150668 KB |
Output is correct |
24 |
Correct |
1227 ms |
150632 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
3284 KB |
Output is correct |
2 |
Correct |
386 ms |
150620 KB |
Output is correct |
3 |
Correct |
1333 ms |
150636 KB |
Output is correct |
4 |
Correct |
566 ms |
150616 KB |
Output is correct |
5 |
Correct |
579 ms |
150732 KB |
Output is correct |
6 |
Correct |
372 ms |
150640 KB |
Output is correct |
7 |
Correct |
362 ms |
150664 KB |
Output is correct |
8 |
Correct |
557 ms |
150636 KB |
Output is correct |
9 |
Correct |
362 ms |
150636 KB |
Output is correct |
10 |
Correct |
571 ms |
150628 KB |
Output is correct |
11 |
Correct |
425 ms |
150640 KB |
Output is correct |
12 |
Correct |
885 ms |
150636 KB |
Output is correct |
13 |
Correct |
435 ms |
150636 KB |
Output is correct |
14 |
Correct |
5 ms |
3284 KB |
Output is correct |
15 |
Correct |
447 ms |
150628 KB |
Output is correct |
16 |
Correct |
381 ms |
150636 KB |
Output is correct |
17 |
Correct |
796 ms |
150628 KB |
Output is correct |
18 |
Correct |
794 ms |
150604 KB |
Output is correct |
19 |
Correct |
384 ms |
150628 KB |
Output is correct |
20 |
Correct |
774 ms |
150628 KB |
Output is correct |
21 |
Correct |
690 ms |
150636 KB |
Output is correct |
22 |
Correct |
759 ms |
150628 KB |
Output is correct |
23 |
Correct |
478 ms |
150668 KB |
Output is correct |
24 |
Correct |
1227 ms |
150632 KB |
Output is correct |
25 |
Correct |
319 ms |
149864 KB |
Output is correct |
26 |
Correct |
425 ms |
150664 KB |
Output is correct |
27 |
Correct |
393 ms |
150620 KB |
Output is correct |
28 |
Correct |
371 ms |
150636 KB |
Output is correct |
29 |
Correct |
412 ms |
150672 KB |
Output is correct |
30 |
Correct |
619 ms |
150632 KB |
Output is correct |
31 |
Correct |
643 ms |
150684 KB |
Output is correct |
32 |
Correct |
1226 ms |
150636 KB |
Output is correct |
33 |
Correct |
2012 ms |
150572 KB |
Output is correct |
34 |
Correct |
2398 ms |
150572 KB |
Output is correct |
35 |
Correct |
1499 ms |
150632 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
3292 KB |
Output is correct |
2 |
Correct |
2998 ms |
1197192 KB |
Output is correct |
3 |
Correct |
2972 ms |
1197180 KB |
Output is correct |
4 |
Correct |
2949 ms |
1197184 KB |
Output is correct |
5 |
Correct |
2480 ms |
1197240 KB |
Output is correct |
6 |
Correct |
2913 ms |
1197184 KB |
Output is correct |
7 |
Correct |
3376 ms |
1197184 KB |
Output is correct |
8 |
Correct |
3 ms |
3284 KB |
Output is correct |
9 |
Correct |
386 ms |
150620 KB |
Output is correct |
10 |
Correct |
1333 ms |
150636 KB |
Output is correct |
11 |
Correct |
566 ms |
150616 KB |
Output is correct |
12 |
Correct |
579 ms |
150732 KB |
Output is correct |
13 |
Correct |
372 ms |
150640 KB |
Output is correct |
14 |
Correct |
362 ms |
150664 KB |
Output is correct |
15 |
Correct |
557 ms |
150636 KB |
Output is correct |
16 |
Correct |
362 ms |
150636 KB |
Output is correct |
17 |
Correct |
571 ms |
150628 KB |
Output is correct |
18 |
Correct |
425 ms |
150640 KB |
Output is correct |
19 |
Correct |
885 ms |
150636 KB |
Output is correct |
20 |
Correct |
435 ms |
150636 KB |
Output is correct |
21 |
Correct |
5 ms |
3284 KB |
Output is correct |
22 |
Correct |
447 ms |
150628 KB |
Output is correct |
23 |
Correct |
381 ms |
150636 KB |
Output is correct |
24 |
Correct |
796 ms |
150628 KB |
Output is correct |
25 |
Correct |
794 ms |
150604 KB |
Output is correct |
26 |
Correct |
384 ms |
150628 KB |
Output is correct |
27 |
Correct |
774 ms |
150628 KB |
Output is correct |
28 |
Correct |
690 ms |
150636 KB |
Output is correct |
29 |
Correct |
759 ms |
150628 KB |
Output is correct |
30 |
Correct |
478 ms |
150668 KB |
Output is correct |
31 |
Correct |
1227 ms |
150632 KB |
Output is correct |
32 |
Correct |
319 ms |
149864 KB |
Output is correct |
33 |
Correct |
425 ms |
150664 KB |
Output is correct |
34 |
Correct |
393 ms |
150620 KB |
Output is correct |
35 |
Correct |
371 ms |
150636 KB |
Output is correct |
36 |
Correct |
412 ms |
150672 KB |
Output is correct |
37 |
Correct |
619 ms |
150632 KB |
Output is correct |
38 |
Correct |
643 ms |
150684 KB |
Output is correct |
39 |
Correct |
1226 ms |
150636 KB |
Output is correct |
40 |
Correct |
2012 ms |
150572 KB |
Output is correct |
41 |
Correct |
2398 ms |
150572 KB |
Output is correct |
42 |
Correct |
1499 ms |
150632 KB |
Output is correct |
43 |
Correct |
0 ms |
340 KB |
Output is correct |
44 |
Correct |
3 ms |
3288 KB |
Output is correct |
45 |
Correct |
3225 ms |
1197192 KB |
Output is correct |
46 |
Correct |
2737 ms |
1197180 KB |
Output is correct |
47 |
Correct |
2749 ms |
1197188 KB |
Output is correct |
48 |
Correct |
3427 ms |
1197184 KB |
Output is correct |
49 |
Correct |
3317 ms |
1197180 KB |
Output is correct |
50 |
Correct |
2951 ms |
1197188 KB |
Output is correct |
51 |
Correct |
2645 ms |
1197180 KB |
Output is correct |
52 |
Correct |
2810 ms |
1197180 KB |
Output is correct |
53 |
Correct |
6045 ms |
1197184 KB |
Output is correct |
54 |
Correct |
4781 ms |
1206216 KB |
Output is correct |
55 |
Correct |
5625 ms |
1205344 KB |
Output is correct |
56 |
Correct |
6560 ms |
1205996 KB |
Output is correct |
57 |
Correct |
6914 ms |
1206128 KB |
Output is correct |
58 |
Correct |
6737 ms |
1206124 KB |
Output is correct |
59 |
Correct |
6453 ms |
1206256 KB |
Output is correct |
60 |
Correct |
6582 ms |
1205544 KB |
Output is correct |
61 |
Correct |
6371 ms |
1205440 KB |
Output is correct |