#include <bits/stdc++.h>
#include "dungeons.h"
using namespace std;
const long long INF = (long long)1e18;
const int logn = 25, bont = 9, M = 3;
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<long long> ut;
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-1);
for(int i = 0; i < bont-1; i++)
calcST(st[i], 1<<(i*M));
ut.resize(n, 0);
for(int i = n-1; i >= 0; i--)
ut[i] = ut[w[i]] + (long long)s[i];
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;
if(y+1 == bont){
ert += ut[x];
break;
}
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 |
9 ms |
10316 KB |
Output is correct |
4 |
Correct |
391 ms |
251280 KB |
Output is correct |
5 |
Correct |
9 ms |
10316 KB |
Output is correct |
6 |
Correct |
370 ms |
251016 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
5324 KB |
Output is correct |
2 |
Correct |
3534 ms |
2007360 KB |
Output is correct |
3 |
Correct |
3396 ms |
2008112 KB |
Output is correct |
4 |
Correct |
3259 ms |
2008028 KB |
Output is correct |
5 |
Correct |
3249 ms |
2008024 KB |
Output is correct |
6 |
Correct |
3586 ms |
2008124 KB |
Output is correct |
7 |
Correct |
3315 ms |
2006760 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
5324 KB |
Output is correct |
2 |
Correct |
457 ms |
251080 KB |
Output is correct |
3 |
Correct |
431 ms |
251220 KB |
Output is correct |
4 |
Correct |
396 ms |
251060 KB |
Output is correct |
5 |
Correct |
409 ms |
251316 KB |
Output is correct |
6 |
Correct |
464 ms |
251184 KB |
Output is correct |
7 |
Correct |
442 ms |
251164 KB |
Output is correct |
8 |
Correct |
410 ms |
251188 KB |
Output is correct |
9 |
Correct |
440 ms |
251104 KB |
Output is correct |
10 |
Correct |
418 ms |
251060 KB |
Output is correct |
11 |
Correct |
486 ms |
251188 KB |
Output is correct |
12 |
Correct |
629 ms |
251188 KB |
Output is correct |
13 |
Correct |
531 ms |
251080 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
5324 KB |
Output is correct |
2 |
Correct |
457 ms |
251080 KB |
Output is correct |
3 |
Correct |
431 ms |
251220 KB |
Output is correct |
4 |
Correct |
396 ms |
251060 KB |
Output is correct |
5 |
Correct |
409 ms |
251316 KB |
Output is correct |
6 |
Correct |
464 ms |
251184 KB |
Output is correct |
7 |
Correct |
442 ms |
251164 KB |
Output is correct |
8 |
Correct |
410 ms |
251188 KB |
Output is correct |
9 |
Correct |
440 ms |
251104 KB |
Output is correct |
10 |
Correct |
418 ms |
251060 KB |
Output is correct |
11 |
Correct |
486 ms |
251188 KB |
Output is correct |
12 |
Correct |
629 ms |
251188 KB |
Output is correct |
13 |
Correct |
531 ms |
251080 KB |
Output is correct |
14 |
Correct |
6 ms |
5324 KB |
Output is correct |
15 |
Correct |
409 ms |
251356 KB |
Output is correct |
16 |
Correct |
432 ms |
251184 KB |
Output is correct |
17 |
Correct |
415 ms |
251332 KB |
Output is correct |
18 |
Correct |
425 ms |
251344 KB |
Output is correct |
19 |
Correct |
450 ms |
251248 KB |
Output is correct |
20 |
Correct |
481 ms |
251060 KB |
Output is correct |
21 |
Correct |
456 ms |
251060 KB |
Output is correct |
22 |
Correct |
452 ms |
251188 KB |
Output is correct |
23 |
Correct |
477 ms |
251152 KB |
Output is correct |
24 |
Correct |
670 ms |
251108 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
5324 KB |
Output is correct |
2 |
Correct |
457 ms |
251080 KB |
Output is correct |
3 |
Correct |
431 ms |
251220 KB |
Output is correct |
4 |
Correct |
396 ms |
251060 KB |
Output is correct |
5 |
Correct |
409 ms |
251316 KB |
Output is correct |
6 |
Correct |
464 ms |
251184 KB |
Output is correct |
7 |
Correct |
442 ms |
251164 KB |
Output is correct |
8 |
Correct |
410 ms |
251188 KB |
Output is correct |
9 |
Correct |
440 ms |
251104 KB |
Output is correct |
10 |
Correct |
418 ms |
251060 KB |
Output is correct |
11 |
Correct |
486 ms |
251188 KB |
Output is correct |
12 |
Correct |
629 ms |
251188 KB |
Output is correct |
13 |
Correct |
531 ms |
251080 KB |
Output is correct |
14 |
Correct |
6 ms |
5324 KB |
Output is correct |
15 |
Correct |
409 ms |
251356 KB |
Output is correct |
16 |
Correct |
432 ms |
251184 KB |
Output is correct |
17 |
Correct |
415 ms |
251332 KB |
Output is correct |
18 |
Correct |
425 ms |
251344 KB |
Output is correct |
19 |
Correct |
450 ms |
251248 KB |
Output is correct |
20 |
Correct |
481 ms |
251060 KB |
Output is correct |
21 |
Correct |
456 ms |
251060 KB |
Output is correct |
22 |
Correct |
452 ms |
251188 KB |
Output is correct |
23 |
Correct |
477 ms |
251152 KB |
Output is correct |
24 |
Correct |
670 ms |
251108 KB |
Output is correct |
25 |
Correct |
383 ms |
250292 KB |
Output is correct |
26 |
Correct |
430 ms |
251184 KB |
Output is correct |
27 |
Correct |
417 ms |
251168 KB |
Output is correct |
28 |
Correct |
421 ms |
251176 KB |
Output is correct |
29 |
Correct |
453 ms |
251100 KB |
Output is correct |
30 |
Correct |
481 ms |
251188 KB |
Output is correct |
31 |
Correct |
496 ms |
251276 KB |
Output is correct |
32 |
Correct |
621 ms |
251320 KB |
Output is correct |
33 |
Correct |
952 ms |
250996 KB |
Output is correct |
34 |
Correct |
1690 ms |
251228 KB |
Output is correct |
35 |
Correct |
745 ms |
251064 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
5324 KB |
Output is correct |
2 |
Correct |
3534 ms |
2007360 KB |
Output is correct |
3 |
Correct |
3396 ms |
2008112 KB |
Output is correct |
4 |
Correct |
3259 ms |
2008028 KB |
Output is correct |
5 |
Correct |
3249 ms |
2008024 KB |
Output is correct |
6 |
Correct |
3586 ms |
2008124 KB |
Output is correct |
7 |
Correct |
3315 ms |
2006760 KB |
Output is correct |
8 |
Correct |
6 ms |
5324 KB |
Output is correct |
9 |
Correct |
457 ms |
251080 KB |
Output is correct |
10 |
Correct |
431 ms |
251220 KB |
Output is correct |
11 |
Correct |
396 ms |
251060 KB |
Output is correct |
12 |
Correct |
409 ms |
251316 KB |
Output is correct |
13 |
Correct |
464 ms |
251184 KB |
Output is correct |
14 |
Correct |
442 ms |
251164 KB |
Output is correct |
15 |
Correct |
410 ms |
251188 KB |
Output is correct |
16 |
Correct |
440 ms |
251104 KB |
Output is correct |
17 |
Correct |
418 ms |
251060 KB |
Output is correct |
18 |
Correct |
486 ms |
251188 KB |
Output is correct |
19 |
Correct |
629 ms |
251188 KB |
Output is correct |
20 |
Correct |
531 ms |
251080 KB |
Output is correct |
21 |
Correct |
6 ms |
5324 KB |
Output is correct |
22 |
Correct |
409 ms |
251356 KB |
Output is correct |
23 |
Correct |
432 ms |
251184 KB |
Output is correct |
24 |
Correct |
415 ms |
251332 KB |
Output is correct |
25 |
Correct |
425 ms |
251344 KB |
Output is correct |
26 |
Correct |
450 ms |
251248 KB |
Output is correct |
27 |
Correct |
481 ms |
251060 KB |
Output is correct |
28 |
Correct |
456 ms |
251060 KB |
Output is correct |
29 |
Correct |
452 ms |
251188 KB |
Output is correct |
30 |
Correct |
477 ms |
251152 KB |
Output is correct |
31 |
Correct |
670 ms |
251108 KB |
Output is correct |
32 |
Correct |
383 ms |
250292 KB |
Output is correct |
33 |
Correct |
430 ms |
251184 KB |
Output is correct |
34 |
Correct |
417 ms |
251168 KB |
Output is correct |
35 |
Correct |
421 ms |
251176 KB |
Output is correct |
36 |
Correct |
453 ms |
251100 KB |
Output is correct |
37 |
Correct |
481 ms |
251188 KB |
Output is correct |
38 |
Correct |
496 ms |
251276 KB |
Output is correct |
39 |
Correct |
621 ms |
251320 KB |
Output is correct |
40 |
Correct |
952 ms |
250996 KB |
Output is correct |
41 |
Correct |
1690 ms |
251228 KB |
Output is correct |
42 |
Correct |
745 ms |
251064 KB |
Output is correct |
43 |
Correct |
0 ms |
204 KB |
Output is correct |
44 |
Correct |
5 ms |
5324 KB |
Output is correct |
45 |
Correct |
3913 ms |
2013324 KB |
Output is correct |
46 |
Correct |
3270 ms |
2008724 KB |
Output is correct |
47 |
Correct |
3272 ms |
2009312 KB |
Output is correct |
48 |
Correct |
3197 ms |
2011212 KB |
Output is correct |
49 |
Correct |
3880 ms |
2013696 KB |
Output is correct |
50 |
Correct |
3509 ms |
2010976 KB |
Output is correct |
51 |
Correct |
3177 ms |
2011528 KB |
Output is correct |
52 |
Correct |
3590 ms |
2009160 KB |
Output is correct |
53 |
Correct |
5843 ms |
2009888 KB |
Output is correct |
54 |
Correct |
4390 ms |
2010948 KB |
Output is correct |
55 |
Correct |
5439 ms |
2009960 KB |
Output is correct |
56 |
Correct |
4810 ms |
2010584 KB |
Output is correct |
57 |
Correct |
5400 ms |
2010696 KB |
Output is correct |
58 |
Correct |
4924 ms |
2010888 KB |
Output is correct |
59 |
Correct |
5020 ms |
2011008 KB |
Output is correct |
60 |
Correct |
5864 ms |
2010128 KB |
Output is correct |
61 |
Correct |
5332 ms |
2009976 KB |
Output is correct |