#include "dungeons.h"
#include <vector>
constexpr int maxn = 4e5+10, logn = 24, log_lift = 12, base_lift = 4;
constexpr int inf = 0x3f3f3f3f;
struct FunctionalGraph {
int f[log_lift][maxn];
int tab[log_lift][maxn];
long long cost[log_lift][maxn];
void add_i(const int& i, const int& x, const int& v, const int& st) { f[0][i] = x, cost[0][i] = v, tab[0][i] = st; }
void build(int n) {
f[0][n] = n;
for(int l = 1; l < log_lift; l++) {
for(int i = 0; i <= n; i++) {
f[l][i] = i;
tab[l][i] = tab[l-1][i];
for(int k = 0; k < base_lift; k++) {
if(tab[l-1][f[l][i]] < inf)
tab[l][i] = std::max(0ll, std::min((long long)tab[l][i], tab[l-1][f[l][i]] - cost[l][i]));
cost[l][i] += cost[l-1][f[l][i]];
f[l][i] = f[l-1][f[l][i]];
}
}
}
}
void go(int& x, long long& val) {
for(int l = log_lift-1; l >= 0; l--)
for(int k = 0; k < base_lift-1; k++)
if(tab[l][x] > val || tab[l][x] == inf) val += cost[l][x], x = f[l][x];
}
} graph[logn];
void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
for(int lg = 0; lg < logn; lg++) {
for(int i = 0; i < n; i++) {
if(s[i] < (2<<lg)) graph[lg].add_i(i, w[i], s[i], inf);
else graph[lg].add_i(i, l[i], p[i], s[i]);
}
graph[lg].build(n);
}
return;
}
long long simulate(int x, int z) {
long long val = z;
for(int lg = 0; lg < logn; lg++)
graph[lg].go(x, val);
return val;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
6604 KB |
Output is correct |
2 |
Correct |
4 ms |
6604 KB |
Output is correct |
3 |
Correct |
15 ms |
15692 KB |
Output is correct |
4 |
Correct |
287 ms |
234472 KB |
Output is correct |
5 |
Correct |
14 ms |
15692 KB |
Output is correct |
6 |
Correct |
296 ms |
234208 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
11228 KB |
Output is correct |
2 |
Correct |
1904 ms |
1824036 KB |
Output is correct |
3 |
Correct |
1805 ms |
1823960 KB |
Output is correct |
4 |
Correct |
2053 ms |
1825604 KB |
Output is correct |
5 |
Correct |
2534 ms |
1825516 KB |
Output is correct |
6 |
Correct |
1883 ms |
1824072 KB |
Output is correct |
7 |
Correct |
1882 ms |
1822360 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
11232 KB |
Output is correct |
2 |
Correct |
675 ms |
235820 KB |
Output is correct |
3 |
Correct |
687 ms |
236044 KB |
Output is correct |
4 |
Correct |
342 ms |
235428 KB |
Output is correct |
5 |
Correct |
358 ms |
235188 KB |
Output is correct |
6 |
Correct |
583 ms |
235432 KB |
Output is correct |
7 |
Correct |
544 ms |
235468 KB |
Output is correct |
8 |
Correct |
376 ms |
235128 KB |
Output is correct |
9 |
Correct |
394 ms |
235180 KB |
Output is correct |
10 |
Correct |
318 ms |
235116 KB |
Output is correct |
11 |
Correct |
445 ms |
235384 KB |
Output is correct |
12 |
Correct |
873 ms |
235588 KB |
Output is correct |
13 |
Correct |
734 ms |
235416 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
11232 KB |
Output is correct |
2 |
Correct |
675 ms |
235820 KB |
Output is correct |
3 |
Correct |
687 ms |
236044 KB |
Output is correct |
4 |
Correct |
342 ms |
235428 KB |
Output is correct |
5 |
Correct |
358 ms |
235188 KB |
Output is correct |
6 |
Correct |
583 ms |
235432 KB |
Output is correct |
7 |
Correct |
544 ms |
235468 KB |
Output is correct |
8 |
Correct |
376 ms |
235128 KB |
Output is correct |
9 |
Correct |
394 ms |
235180 KB |
Output is correct |
10 |
Correct |
318 ms |
235116 KB |
Output is correct |
11 |
Correct |
445 ms |
235384 KB |
Output is correct |
12 |
Correct |
873 ms |
235588 KB |
Output is correct |
13 |
Correct |
734 ms |
235416 KB |
Output is correct |
14 |
Correct |
10 ms |
11212 KB |
Output is correct |
15 |
Correct |
548 ms |
235616 KB |
Output is correct |
16 |
Correct |
708 ms |
235868 KB |
Output is correct |
17 |
Correct |
456 ms |
235316 KB |
Output is correct |
18 |
Correct |
488 ms |
235480 KB |
Output is correct |
19 |
Correct |
550 ms |
235460 KB |
Output is correct |
20 |
Correct |
447 ms |
235204 KB |
Output is correct |
21 |
Correct |
470 ms |
235332 KB |
Output is correct |
22 |
Correct |
380 ms |
235332 KB |
Output is correct |
23 |
Correct |
476 ms |
235556 KB |
Output is correct |
24 |
Correct |
880 ms |
235472 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
11232 KB |
Output is correct |
2 |
Correct |
675 ms |
235820 KB |
Output is correct |
3 |
Correct |
687 ms |
236044 KB |
Output is correct |
4 |
Correct |
342 ms |
235428 KB |
Output is correct |
5 |
Correct |
358 ms |
235188 KB |
Output is correct |
6 |
Correct |
583 ms |
235432 KB |
Output is correct |
7 |
Correct |
544 ms |
235468 KB |
Output is correct |
8 |
Correct |
376 ms |
235128 KB |
Output is correct |
9 |
Correct |
394 ms |
235180 KB |
Output is correct |
10 |
Correct |
318 ms |
235116 KB |
Output is correct |
11 |
Correct |
445 ms |
235384 KB |
Output is correct |
12 |
Correct |
873 ms |
235588 KB |
Output is correct |
13 |
Correct |
734 ms |
235416 KB |
Output is correct |
14 |
Correct |
10 ms |
11212 KB |
Output is correct |
15 |
Correct |
548 ms |
235616 KB |
Output is correct |
16 |
Correct |
708 ms |
235868 KB |
Output is correct |
17 |
Correct |
456 ms |
235316 KB |
Output is correct |
18 |
Correct |
488 ms |
235480 KB |
Output is correct |
19 |
Correct |
550 ms |
235460 KB |
Output is correct |
20 |
Correct |
447 ms |
235204 KB |
Output is correct |
21 |
Correct |
470 ms |
235332 KB |
Output is correct |
22 |
Correct |
380 ms |
235332 KB |
Output is correct |
23 |
Correct |
476 ms |
235556 KB |
Output is correct |
24 |
Correct |
880 ms |
235472 KB |
Output is correct |
25 |
Correct |
325 ms |
234692 KB |
Output is correct |
26 |
Correct |
715 ms |
235848 KB |
Output is correct |
27 |
Correct |
480 ms |
235332 KB |
Output is correct |
28 |
Correct |
421 ms |
235312 KB |
Output is correct |
29 |
Correct |
724 ms |
235688 KB |
Output is correct |
30 |
Correct |
400 ms |
235576 KB |
Output is correct |
31 |
Correct |
418 ms |
235104 KB |
Output is correct |
32 |
Correct |
709 ms |
235312 KB |
Output is correct |
33 |
Correct |
692 ms |
235372 KB |
Output is correct |
34 |
Correct |
915 ms |
235132 KB |
Output is correct |
35 |
Correct |
775 ms |
235380 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
11228 KB |
Output is correct |
2 |
Correct |
1904 ms |
1824036 KB |
Output is correct |
3 |
Correct |
1805 ms |
1823960 KB |
Output is correct |
4 |
Correct |
2053 ms |
1825604 KB |
Output is correct |
5 |
Correct |
2534 ms |
1825516 KB |
Output is correct |
6 |
Correct |
1883 ms |
1824072 KB |
Output is correct |
7 |
Correct |
1882 ms |
1822360 KB |
Output is correct |
8 |
Correct |
11 ms |
11232 KB |
Output is correct |
9 |
Correct |
675 ms |
235820 KB |
Output is correct |
10 |
Correct |
687 ms |
236044 KB |
Output is correct |
11 |
Correct |
342 ms |
235428 KB |
Output is correct |
12 |
Correct |
358 ms |
235188 KB |
Output is correct |
13 |
Correct |
583 ms |
235432 KB |
Output is correct |
14 |
Correct |
544 ms |
235468 KB |
Output is correct |
15 |
Correct |
376 ms |
235128 KB |
Output is correct |
16 |
Correct |
394 ms |
235180 KB |
Output is correct |
17 |
Correct |
318 ms |
235116 KB |
Output is correct |
18 |
Correct |
445 ms |
235384 KB |
Output is correct |
19 |
Correct |
873 ms |
235588 KB |
Output is correct |
20 |
Correct |
734 ms |
235416 KB |
Output is correct |
21 |
Correct |
10 ms |
11212 KB |
Output is correct |
22 |
Correct |
548 ms |
235616 KB |
Output is correct |
23 |
Correct |
708 ms |
235868 KB |
Output is correct |
24 |
Correct |
456 ms |
235316 KB |
Output is correct |
25 |
Correct |
488 ms |
235480 KB |
Output is correct |
26 |
Correct |
550 ms |
235460 KB |
Output is correct |
27 |
Correct |
447 ms |
235204 KB |
Output is correct |
28 |
Correct |
470 ms |
235332 KB |
Output is correct |
29 |
Correct |
380 ms |
235332 KB |
Output is correct |
30 |
Correct |
476 ms |
235556 KB |
Output is correct |
31 |
Correct |
880 ms |
235472 KB |
Output is correct |
32 |
Correct |
325 ms |
234692 KB |
Output is correct |
33 |
Correct |
715 ms |
235848 KB |
Output is correct |
34 |
Correct |
480 ms |
235332 KB |
Output is correct |
35 |
Correct |
421 ms |
235312 KB |
Output is correct |
36 |
Correct |
724 ms |
235688 KB |
Output is correct |
37 |
Correct |
400 ms |
235576 KB |
Output is correct |
38 |
Correct |
418 ms |
235104 KB |
Output is correct |
39 |
Correct |
709 ms |
235312 KB |
Output is correct |
40 |
Correct |
692 ms |
235372 KB |
Output is correct |
41 |
Correct |
915 ms |
235132 KB |
Output is correct |
42 |
Correct |
775 ms |
235380 KB |
Output is correct |
43 |
Correct |
3 ms |
6572 KB |
Output is correct |
44 |
Correct |
11 ms |
11184 KB |
Output is correct |
45 |
Correct |
4014 ms |
1828780 KB |
Output is correct |
46 |
Correct |
2519 ms |
1824348 KB |
Output is correct |
47 |
Correct |
2587 ms |
1824480 KB |
Output is correct |
48 |
Correct |
2666 ms |
1826672 KB |
Output is correct |
49 |
Correct |
4048 ms |
1828868 KB |
Output is correct |
50 |
Correct |
1860 ms |
1826300 KB |
Output is correct |
51 |
Correct |
2338 ms |
1826772 KB |
Output is correct |
52 |
Correct |
1852 ms |
1824520 KB |
Output is correct |
53 |
Correct |
5404 ms |
1823104 KB |
Output is correct |
54 |
Correct |
2732 ms |
1821956 KB |
Output is correct |
55 |
Correct |
2787 ms |
1821692 KB |
Output is correct |
56 |
Correct |
4749 ms |
1821052 KB |
Output is correct |
57 |
Correct |
4768 ms |
1820296 KB |
Output is correct |
58 |
Correct |
4800 ms |
1819396 KB |
Output is correct |
59 |
Correct |
4910 ms |
1818512 KB |
Output is correct |
60 |
Correct |
4954 ms |
1817916 KB |
Output is correct |
61 |
Correct |
3513 ms |
1817092 KB |
Output is correct |