#include <bits/stdc++.h>
#include "dungeons.h"
using namespace std;
const long long INF = (long long)1e18;
const int logn = 25, bont = 7, M = 4;
struct adat{
int ind;
long long legk, ossz;
adat() {}
adat(int ind, long long legk, long long ossz) : ind(ind), legk(legk), ossz(ossz) {}
};
inline adat merge(adat a, adat b){
return adat(b.ind, min(a.legk, b.legk-a.ossz), a.ossz+b.ossz);
}
vector<vector<vector<adat>>> st;
vector<int> s, p, w, l;
int n;
void calcST(vector<vector<adat>> &v, int k){
v.resize(n, vector<adat>(logn));
for(int i = 0; i < n; i++){
if(s[i] <= k)
v[i][0] = adat(w[i], INF, s[i]);
else
v[i][0] = adat(l[i], s[i], p[i]);
}
for(int j = 1; j < logn; j++)
for(int i = 0; i < n; i++)
v[i][j] = merge(v[i][j-1], v[v[i][j-1].ind][j-1]);
}
void init(int N, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L) {
n = N;
s = S;
p = P;
w = W;
l = L;
s.push_back(0);
p.push_back(0);
w.push_back(n);
l.push_back(n);
++n;
st.resize(bont);
for(int i = 0; i < bont; i++)
calcST(st[i], 1<<(i*M));
return;
}
long long simulate(int x, int z) {
int y = 0;
long long ert = z;
while (x != n-1)
{
while (y+1 < bont && 1ll<<((y+1)*M) <= ert)
++y;
for(int i = logn-1; i >= 0; i--){
if(st[y][x][i].legk > ert){
ert += st[y][x][i].ossz;
x = st[y][x][i].ind;
}
}
ert += (long long)s[x];
x = w[x];
}
return ert;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
11 ms |
8992 KB |
Output is correct |
4 |
Correct |
332 ms |
220012 KB |
Output is correct |
5 |
Correct |
8 ms |
9036 KB |
Output is correct |
6 |
Correct |
327 ms |
219824 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
4684 KB |
Output is correct |
2 |
Correct |
3151 ms |
1756052 KB |
Output is correct |
3 |
Correct |
2997 ms |
1755912 KB |
Output is correct |
4 |
Correct |
2827 ms |
1756036 KB |
Output is correct |
5 |
Correct |
2908 ms |
1756016 KB |
Output is correct |
6 |
Correct |
3161 ms |
1756028 KB |
Output is correct |
7 |
Correct |
2881 ms |
1755900 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4684 KB |
Output is correct |
2 |
Correct |
416 ms |
220172 KB |
Output is correct |
3 |
Correct |
405 ms |
220152 KB |
Output is correct |
4 |
Correct |
371 ms |
220196 KB |
Output is correct |
5 |
Correct |
364 ms |
220128 KB |
Output is correct |
6 |
Correct |
433 ms |
220188 KB |
Output is correct |
7 |
Correct |
412 ms |
220212 KB |
Output is correct |
8 |
Correct |
378 ms |
220180 KB |
Output is correct |
9 |
Correct |
375 ms |
220372 KB |
Output is correct |
10 |
Correct |
389 ms |
220132 KB |
Output is correct |
11 |
Correct |
414 ms |
220168 KB |
Output is correct |
12 |
Correct |
601 ms |
219956 KB |
Output is correct |
13 |
Correct |
455 ms |
219880 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4684 KB |
Output is correct |
2 |
Correct |
416 ms |
220172 KB |
Output is correct |
3 |
Correct |
405 ms |
220152 KB |
Output is correct |
4 |
Correct |
371 ms |
220196 KB |
Output is correct |
5 |
Correct |
364 ms |
220128 KB |
Output is correct |
6 |
Correct |
433 ms |
220188 KB |
Output is correct |
7 |
Correct |
412 ms |
220212 KB |
Output is correct |
8 |
Correct |
378 ms |
220180 KB |
Output is correct |
9 |
Correct |
375 ms |
220372 KB |
Output is correct |
10 |
Correct |
389 ms |
220132 KB |
Output is correct |
11 |
Correct |
414 ms |
220168 KB |
Output is correct |
12 |
Correct |
601 ms |
219956 KB |
Output is correct |
13 |
Correct |
455 ms |
219880 KB |
Output is correct |
14 |
Correct |
5 ms |
4684 KB |
Output is correct |
15 |
Correct |
368 ms |
219816 KB |
Output is correct |
16 |
Correct |
417 ms |
219828 KB |
Output is correct |
17 |
Correct |
386 ms |
219768 KB |
Output is correct |
18 |
Correct |
382 ms |
219848 KB |
Output is correct |
19 |
Correct |
427 ms |
219784 KB |
Output is correct |
20 |
Correct |
407 ms |
219824 KB |
Output is correct |
21 |
Correct |
472 ms |
219820 KB |
Output is correct |
22 |
Correct |
435 ms |
219832 KB |
Output is correct |
23 |
Correct |
417 ms |
219744 KB |
Output is correct |
24 |
Correct |
591 ms |
219952 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4684 KB |
Output is correct |
2 |
Correct |
416 ms |
220172 KB |
Output is correct |
3 |
Correct |
405 ms |
220152 KB |
Output is correct |
4 |
Correct |
371 ms |
220196 KB |
Output is correct |
5 |
Correct |
364 ms |
220128 KB |
Output is correct |
6 |
Correct |
433 ms |
220188 KB |
Output is correct |
7 |
Correct |
412 ms |
220212 KB |
Output is correct |
8 |
Correct |
378 ms |
220180 KB |
Output is correct |
9 |
Correct |
375 ms |
220372 KB |
Output is correct |
10 |
Correct |
389 ms |
220132 KB |
Output is correct |
11 |
Correct |
414 ms |
220168 KB |
Output is correct |
12 |
Correct |
601 ms |
219956 KB |
Output is correct |
13 |
Correct |
455 ms |
219880 KB |
Output is correct |
14 |
Correct |
5 ms |
4684 KB |
Output is correct |
15 |
Correct |
368 ms |
219816 KB |
Output is correct |
16 |
Correct |
417 ms |
219828 KB |
Output is correct |
17 |
Correct |
386 ms |
219768 KB |
Output is correct |
18 |
Correct |
382 ms |
219848 KB |
Output is correct |
19 |
Correct |
427 ms |
219784 KB |
Output is correct |
20 |
Correct |
407 ms |
219824 KB |
Output is correct |
21 |
Correct |
472 ms |
219820 KB |
Output is correct |
22 |
Correct |
435 ms |
219832 KB |
Output is correct |
23 |
Correct |
417 ms |
219744 KB |
Output is correct |
24 |
Correct |
591 ms |
219952 KB |
Output is correct |
25 |
Correct |
341 ms |
219148 KB |
Output is correct |
26 |
Correct |
418 ms |
219828 KB |
Output is correct |
27 |
Correct |
379 ms |
219868 KB |
Output is correct |
28 |
Correct |
402 ms |
219760 KB |
Output is correct |
29 |
Correct |
422 ms |
219776 KB |
Output is correct |
30 |
Correct |
422 ms |
219848 KB |
Output is correct |
31 |
Correct |
435 ms |
219932 KB |
Output is correct |
32 |
Correct |
538 ms |
219844 KB |
Output is correct |
33 |
Correct |
1038 ms |
219784 KB |
Output is correct |
34 |
Correct |
1564 ms |
219828 KB |
Output is correct |
35 |
Correct |
1178 ms |
219740 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
4684 KB |
Output is correct |
2 |
Correct |
3151 ms |
1756052 KB |
Output is correct |
3 |
Correct |
2997 ms |
1755912 KB |
Output is correct |
4 |
Correct |
2827 ms |
1756036 KB |
Output is correct |
5 |
Correct |
2908 ms |
1756016 KB |
Output is correct |
6 |
Correct |
3161 ms |
1756028 KB |
Output is correct |
7 |
Correct |
2881 ms |
1755900 KB |
Output is correct |
8 |
Correct |
6 ms |
4684 KB |
Output is correct |
9 |
Correct |
416 ms |
220172 KB |
Output is correct |
10 |
Correct |
405 ms |
220152 KB |
Output is correct |
11 |
Correct |
371 ms |
220196 KB |
Output is correct |
12 |
Correct |
364 ms |
220128 KB |
Output is correct |
13 |
Correct |
433 ms |
220188 KB |
Output is correct |
14 |
Correct |
412 ms |
220212 KB |
Output is correct |
15 |
Correct |
378 ms |
220180 KB |
Output is correct |
16 |
Correct |
375 ms |
220372 KB |
Output is correct |
17 |
Correct |
389 ms |
220132 KB |
Output is correct |
18 |
Correct |
414 ms |
220168 KB |
Output is correct |
19 |
Correct |
601 ms |
219956 KB |
Output is correct |
20 |
Correct |
455 ms |
219880 KB |
Output is correct |
21 |
Correct |
5 ms |
4684 KB |
Output is correct |
22 |
Correct |
368 ms |
219816 KB |
Output is correct |
23 |
Correct |
417 ms |
219828 KB |
Output is correct |
24 |
Correct |
386 ms |
219768 KB |
Output is correct |
25 |
Correct |
382 ms |
219848 KB |
Output is correct |
26 |
Correct |
427 ms |
219784 KB |
Output is correct |
27 |
Correct |
407 ms |
219824 KB |
Output is correct |
28 |
Correct |
472 ms |
219820 KB |
Output is correct |
29 |
Correct |
435 ms |
219832 KB |
Output is correct |
30 |
Correct |
417 ms |
219744 KB |
Output is correct |
31 |
Correct |
591 ms |
219952 KB |
Output is correct |
32 |
Correct |
341 ms |
219148 KB |
Output is correct |
33 |
Correct |
418 ms |
219828 KB |
Output is correct |
34 |
Correct |
379 ms |
219868 KB |
Output is correct |
35 |
Correct |
402 ms |
219760 KB |
Output is correct |
36 |
Correct |
422 ms |
219776 KB |
Output is correct |
37 |
Correct |
422 ms |
219848 KB |
Output is correct |
38 |
Correct |
435 ms |
219932 KB |
Output is correct |
39 |
Correct |
538 ms |
219844 KB |
Output is correct |
40 |
Correct |
1038 ms |
219784 KB |
Output is correct |
41 |
Correct |
1564 ms |
219828 KB |
Output is correct |
42 |
Correct |
1178 ms |
219740 KB |
Output is correct |
43 |
Correct |
0 ms |
204 KB |
Output is correct |
44 |
Correct |
5 ms |
4684 KB |
Output is correct |
45 |
Correct |
3319 ms |
1756100 KB |
Output is correct |
46 |
Correct |
2887 ms |
1756152 KB |
Output is correct |
47 |
Correct |
2890 ms |
1756232 KB |
Output is correct |
48 |
Correct |
2847 ms |
1756220 KB |
Output is correct |
49 |
Correct |
3429 ms |
1756148 KB |
Output is correct |
50 |
Correct |
3125 ms |
1755936 KB |
Output is correct |
51 |
Correct |
2802 ms |
1755648 KB |
Output is correct |
52 |
Correct |
3098 ms |
1755228 KB |
Output is correct |
53 |
Correct |
4621 ms |
1754752 KB |
Output is correct |
54 |
Correct |
4053 ms |
1754252 KB |
Output is correct |
55 |
Correct |
4978 ms |
1753692 KB |
Output is correct |
56 |
Correct |
5376 ms |
1753224 KB |
Output is correct |
57 |
Correct |
4582 ms |
1752936 KB |
Output is correct |
58 |
Correct |
4855 ms |
1752548 KB |
Output is correct |
59 |
Correct |
4629 ms |
1752236 KB |
Output is correct |
60 |
Correct |
6686 ms |
1751732 KB |
Output is correct |
61 |
Correct |
6397 ms |
1751288 KB |
Output is correct |