#include <bits/stdc++.h>
#include "dungeons.h"
using namespace std;
const int mxN = (int)5e4+5;
const int lg = (int)32;
long long lim[mxN][lg][32];
long long gget[mxN][lg][32];
int jump[mxN][lg][32];
int N;
vector<int>S; vector<int>P; vector<int>W; vector<int>L;
void init(int n, vector<int>s, vector<int>p, vector<int>w, vector<int>l) {
S = s, P = p, W = w, L = l;
N = n;
for(int j = 0 ; j < lg ; j++) {
for(int i = 0 ; i < n ; i++) {
if(pow(2,j) >= s[i]) {
lim[i][j][0] = LLONG_MAX;
gget[i][j][0] = s[i];
jump[i][j][0] = w[i];
} else {
lim[i][j][0] = s[i];
gget[i][j][0] = p[i];
jump[i][j][0] = l[i];
}
}
}
for(int k = 1 ; k < 30 ; k++) {
for(int j = 0 ; j < lg ; j++) {
for(int i = 0 ; i < n ; i++) {
lim[i][j][k] = (lim[i][j][k-1] == LLONG_MAX && lim[ jump[i][j][k-1] ][j][k-1] - gget[i][j][k-1] == LLONG_MAX ? LLONG_MAX : min(lim[i][j][k-1], lim[ jump[i][j][k-1] ][j][k-1] - gget[i][j][k-1]));
gget[i][j][k] = gget[i][j][k-1] + gget[ jump[i][j][k-1] ][j][k-1];
jump[i][j][k] = jump[ jump[i][j][k-1] ][j][k-1];
}
}
}
}
long long simulate(int x, int z) {
long long c = z;
int pw = 0;
while(x != N) {
while(pow(2,(pw+1)) <= c && pw+1 <= 30) {
pw++;
}
for(int j = 30 ; j >= 0 ; j--) {
if(lim[x][pw][j] > c && jump[x][pw][j] != N) {
c += gget[x][pw][j];
x = jump[x][pw][j];
}
}
if(x != N) {
if(c >= S[x]) {
c += S[x];
x = W[x];
} else {
c += P[x];
x = L[x];
}
}
}
return c;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
92 ms |
40472 KB |
Output is correct |
4 |
Correct |
2667 ms |
1004612 KB |
Output is correct |
5 |
Correct |
108 ms |
40472 KB |
Output is correct |
6 |
Correct |
2730 ms |
1004612 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
45 ms |
20412 KB |
Output is correct |
2 |
Runtime error |
970 ms |
988796 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
47 ms |
20308 KB |
Output is correct |
2 |
Correct |
3132 ms |
1005324 KB |
Output is correct |
3 |
Correct |
2632 ms |
1005760 KB |
Output is correct |
4 |
Correct |
2734 ms |
1006584 KB |
Output is correct |
5 |
Correct |
2679 ms |
1006412 KB |
Output is correct |
6 |
Correct |
2860 ms |
1006688 KB |
Output is correct |
7 |
Correct |
3001 ms |
1006664 KB |
Output is correct |
8 |
Correct |
2799 ms |
1006488 KB |
Output is correct |
9 |
Correct |
2599 ms |
1006400 KB |
Output is correct |
10 |
Correct |
2715 ms |
1006288 KB |
Output is correct |
11 |
Correct |
3902 ms |
1006792 KB |
Output is correct |
12 |
Correct |
4089 ms |
1006664 KB |
Output is correct |
13 |
Correct |
2947 ms |
1006644 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
47 ms |
20308 KB |
Output is correct |
2 |
Correct |
3132 ms |
1005324 KB |
Output is correct |
3 |
Correct |
2632 ms |
1005760 KB |
Output is correct |
4 |
Correct |
2734 ms |
1006584 KB |
Output is correct |
5 |
Correct |
2679 ms |
1006412 KB |
Output is correct |
6 |
Correct |
2860 ms |
1006688 KB |
Output is correct |
7 |
Correct |
3001 ms |
1006664 KB |
Output is correct |
8 |
Correct |
2799 ms |
1006488 KB |
Output is correct |
9 |
Correct |
2599 ms |
1006400 KB |
Output is correct |
10 |
Correct |
2715 ms |
1006288 KB |
Output is correct |
11 |
Correct |
3902 ms |
1006792 KB |
Output is correct |
12 |
Correct |
4089 ms |
1006664 KB |
Output is correct |
13 |
Correct |
2947 ms |
1006644 KB |
Output is correct |
14 |
Correct |
50 ms |
20436 KB |
Output is correct |
15 |
Correct |
2809 ms |
1006792 KB |
Output is correct |
16 |
Correct |
3292 ms |
1007124 KB |
Output is correct |
17 |
Correct |
2695 ms |
1006516 KB |
Output is correct |
18 |
Correct |
2791 ms |
1006540 KB |
Output is correct |
19 |
Correct |
2941 ms |
1006660 KB |
Output is correct |
20 |
Correct |
2813 ms |
1006404 KB |
Output is correct |
21 |
Correct |
2777 ms |
1006532 KB |
Output is correct |
22 |
Correct |
2858 ms |
1006536 KB |
Output is correct |
23 |
Correct |
3796 ms |
1006760 KB |
Output is correct |
24 |
Correct |
3979 ms |
1006660 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
47 ms |
20308 KB |
Output is correct |
2 |
Correct |
3132 ms |
1005324 KB |
Output is correct |
3 |
Correct |
2632 ms |
1005760 KB |
Output is correct |
4 |
Correct |
2734 ms |
1006584 KB |
Output is correct |
5 |
Correct |
2679 ms |
1006412 KB |
Output is correct |
6 |
Correct |
2860 ms |
1006688 KB |
Output is correct |
7 |
Correct |
3001 ms |
1006664 KB |
Output is correct |
8 |
Correct |
2799 ms |
1006488 KB |
Output is correct |
9 |
Correct |
2599 ms |
1006400 KB |
Output is correct |
10 |
Correct |
2715 ms |
1006288 KB |
Output is correct |
11 |
Correct |
3902 ms |
1006792 KB |
Output is correct |
12 |
Correct |
4089 ms |
1006664 KB |
Output is correct |
13 |
Correct |
2947 ms |
1006644 KB |
Output is correct |
14 |
Correct |
50 ms |
20436 KB |
Output is correct |
15 |
Correct |
2809 ms |
1006792 KB |
Output is correct |
16 |
Correct |
3292 ms |
1007124 KB |
Output is correct |
17 |
Correct |
2695 ms |
1006516 KB |
Output is correct |
18 |
Correct |
2791 ms |
1006540 KB |
Output is correct |
19 |
Correct |
2941 ms |
1006660 KB |
Output is correct |
20 |
Correct |
2813 ms |
1006404 KB |
Output is correct |
21 |
Correct |
2777 ms |
1006532 KB |
Output is correct |
22 |
Correct |
2858 ms |
1006536 KB |
Output is correct |
23 |
Correct |
3796 ms |
1006760 KB |
Output is correct |
24 |
Correct |
3979 ms |
1006660 KB |
Output is correct |
25 |
Correct |
2991 ms |
1005984 KB |
Output is correct |
26 |
Correct |
3115 ms |
1007012 KB |
Output is correct |
27 |
Correct |
2729 ms |
1006456 KB |
Output is correct |
28 |
Correct |
2619 ms |
1006524 KB |
Output is correct |
29 |
Correct |
3034 ms |
1006920 KB |
Output is correct |
30 |
Correct |
3011 ms |
1006664 KB |
Output is correct |
31 |
Correct |
2995 ms |
1006512 KB |
Output is correct |
32 |
Correct |
3967 ms |
1006536 KB |
Output is correct |
33 |
Correct |
3237 ms |
1006264 KB |
Output is correct |
34 |
Correct |
3838 ms |
1006112 KB |
Output is correct |
35 |
Correct |
3539 ms |
1006552 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
45 ms |
20412 KB |
Output is correct |
2 |
Runtime error |
970 ms |
988796 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |