#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int B = 16, L = 7, INF = 0x3f3f3f3f;
const int maxn = 400005;
int n, lim[L], s[maxn], p[maxn], w[maxn], l[maxn];
struct node {
int to; ll sum; int req;
node operator + (const node b) const {
return (node){b.to, sum + b.sum, b.req == INF ? req : max(0LL, min((ll)req, b.req - sum))};
}
} f[L][25][maxn];
void init(int _n, vector<int> _s, vector<int> _p, vector<int> _w, vector<int> _l) {
n = _n, w[n] = l[n] = n;
for (int i = 0; i < n; i++) {
s[i] = _s[i], p[i] = _p[i], w[i] = _w[i], l[i] = _l[i];
}
auto init = [&](int X, node g[][maxn]) {
for (int i = 0; i < n; i++) {
g[0][i] = X >= s[i] ? node{w[i], s[i], INF} : node{l[i], p[i], s[i]};
}
for (int k = 1; k < 25; k++) {
for (int i = 0; i < n; i++) {
g[k][i] = g[k - 1][i] + g[k - 1][g[k - 1][i].to];
}
}
};
for (int d = 0; d < L; d++) {
init(lim[d] = !d ? 1 : lim[d - 1] * B, f[d]);
}
}
ll simulate(int x, int _z) {
ll z = _z;
int i = 0;
while (x < n) {
while (i + 1 < L && z >= lim[i + 1]) i++;
for (int j = 24; ~j; j--) {
if (f[i][j][x].to == n || f[i][j][x].req != INF && f[i][j][x].req <= z) continue;
z += f[i][j][x].sum, x = f[i][j][x].to;
}
if (z >= s[x]) z += s[x], x = w[x];
else z += p[x], x = l[x];
}
return z;
}
Compilation message
dungeons.cpp: In member function 'node node::operator+(node) const':
dungeons.cpp:13:55: warning: narrowing conversion of '((((int)b.node::req) == ((int)INF)) ? ((long long int)((int)((const node*)this)->node::req)) : ((long long int)std::max<long long int>(0, (* & std::min<long long int>(((ll)((int)((const node*)this)->node::req)), (((long long int)((int)b.node::req)) - ((long long int)((const node*)this)->node::sum)))))))' from 'long long int' to 'int' [-Wnarrowing]
13 | return (node){b.to, sum + b.sum, b.req == INF ? req : max(0LL, min((ll)req, b.req - sum))};
| ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dungeons.cpp: In function 'll simulate(int, int)':
dungeons.cpp:43:61: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
43 | if (f[i][j][x].to == n || f[i][j][x].req != INF && f[i][j][x].req <= z) continue;
| ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1612 KB |
Output is correct |
2 |
Correct |
1 ms |
1740 KB |
Output is correct |
3 |
Correct |
6 ms |
10032 KB |
Output is correct |
4 |
Correct |
117 ms |
210600 KB |
Output is correct |
5 |
Correct |
8 ms |
10060 KB |
Output is correct |
6 |
Correct |
135 ms |
210340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5836 KB |
Output is correct |
2 |
Correct |
1259 ms |
1670508 KB |
Output is correct |
3 |
Correct |
1079 ms |
1670704 KB |
Output is correct |
4 |
Correct |
1027 ms |
1672228 KB |
Output is correct |
5 |
Correct |
1153 ms |
1672172 KB |
Output is correct |
6 |
Correct |
1071 ms |
1670552 KB |
Output is correct |
7 |
Correct |
1074 ms |
1668836 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5836 KB |
Output is correct |
2 |
Correct |
264 ms |
212020 KB |
Output is correct |
3 |
Correct |
217 ms |
212144 KB |
Output is correct |
4 |
Correct |
160 ms |
211464 KB |
Output is correct |
5 |
Correct |
170 ms |
211496 KB |
Output is correct |
6 |
Correct |
243 ms |
211624 KB |
Output is correct |
7 |
Correct |
216 ms |
211516 KB |
Output is correct |
8 |
Correct |
176 ms |
211268 KB |
Output is correct |
9 |
Correct |
172 ms |
211264 KB |
Output is correct |
10 |
Correct |
197 ms |
211136 KB |
Output is correct |
11 |
Correct |
218 ms |
211528 KB |
Output is correct |
12 |
Correct |
272 ms |
211756 KB |
Output is correct |
13 |
Correct |
205 ms |
211528 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5836 KB |
Output is correct |
2 |
Correct |
264 ms |
212020 KB |
Output is correct |
3 |
Correct |
217 ms |
212144 KB |
Output is correct |
4 |
Correct |
160 ms |
211464 KB |
Output is correct |
5 |
Correct |
170 ms |
211496 KB |
Output is correct |
6 |
Correct |
243 ms |
211624 KB |
Output is correct |
7 |
Correct |
216 ms |
211516 KB |
Output is correct |
8 |
Correct |
176 ms |
211268 KB |
Output is correct |
9 |
Correct |
172 ms |
211264 KB |
Output is correct |
10 |
Correct |
197 ms |
211136 KB |
Output is correct |
11 |
Correct |
218 ms |
211528 KB |
Output is correct |
12 |
Correct |
272 ms |
211756 KB |
Output is correct |
13 |
Correct |
205 ms |
211528 KB |
Output is correct |
14 |
Correct |
4 ms |
5836 KB |
Output is correct |
15 |
Correct |
168 ms |
211704 KB |
Output is correct |
16 |
Correct |
251 ms |
211932 KB |
Output is correct |
17 |
Correct |
167 ms |
211388 KB |
Output is correct |
18 |
Correct |
161 ms |
211496 KB |
Output is correct |
19 |
Correct |
238 ms |
211580 KB |
Output is correct |
20 |
Correct |
192 ms |
211260 KB |
Output is correct |
21 |
Correct |
212 ms |
211436 KB |
Output is correct |
22 |
Correct |
269 ms |
211368 KB |
Output is correct |
23 |
Correct |
194 ms |
211524 KB |
Output is correct |
24 |
Correct |
280 ms |
211528 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5836 KB |
Output is correct |
2 |
Correct |
264 ms |
212020 KB |
Output is correct |
3 |
Correct |
217 ms |
212144 KB |
Output is correct |
4 |
Correct |
160 ms |
211464 KB |
Output is correct |
5 |
Correct |
170 ms |
211496 KB |
Output is correct |
6 |
Correct |
243 ms |
211624 KB |
Output is correct |
7 |
Correct |
216 ms |
211516 KB |
Output is correct |
8 |
Correct |
176 ms |
211268 KB |
Output is correct |
9 |
Correct |
172 ms |
211264 KB |
Output is correct |
10 |
Correct |
197 ms |
211136 KB |
Output is correct |
11 |
Correct |
218 ms |
211528 KB |
Output is correct |
12 |
Correct |
272 ms |
211756 KB |
Output is correct |
13 |
Correct |
205 ms |
211528 KB |
Output is correct |
14 |
Correct |
4 ms |
5836 KB |
Output is correct |
15 |
Correct |
168 ms |
211704 KB |
Output is correct |
16 |
Correct |
251 ms |
211932 KB |
Output is correct |
17 |
Correct |
167 ms |
211388 KB |
Output is correct |
18 |
Correct |
161 ms |
211496 KB |
Output is correct |
19 |
Correct |
238 ms |
211580 KB |
Output is correct |
20 |
Correct |
192 ms |
211260 KB |
Output is correct |
21 |
Correct |
212 ms |
211436 KB |
Output is correct |
22 |
Correct |
269 ms |
211368 KB |
Output is correct |
23 |
Correct |
194 ms |
211524 KB |
Output is correct |
24 |
Correct |
280 ms |
211528 KB |
Output is correct |
25 |
Correct |
148 ms |
210864 KB |
Output is correct |
26 |
Correct |
224 ms |
212012 KB |
Output is correct |
27 |
Correct |
176 ms |
211388 KB |
Output is correct |
28 |
Correct |
173 ms |
211380 KB |
Output is correct |
29 |
Correct |
242 ms |
211768 KB |
Output is correct |
30 |
Correct |
202 ms |
211508 KB |
Output is correct |
31 |
Correct |
197 ms |
211264 KB |
Output is correct |
32 |
Correct |
313 ms |
211396 KB |
Output is correct |
33 |
Correct |
1006 ms |
211440 KB |
Output is correct |
34 |
Correct |
1262 ms |
211364 KB |
Output is correct |
35 |
Correct |
1405 ms |
211452 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5836 KB |
Output is correct |
2 |
Correct |
1259 ms |
1670508 KB |
Output is correct |
3 |
Correct |
1079 ms |
1670704 KB |
Output is correct |
4 |
Correct |
1027 ms |
1672228 KB |
Output is correct |
5 |
Correct |
1153 ms |
1672172 KB |
Output is correct |
6 |
Correct |
1071 ms |
1670552 KB |
Output is correct |
7 |
Correct |
1074 ms |
1668836 KB |
Output is correct |
8 |
Correct |
4 ms |
5836 KB |
Output is correct |
9 |
Correct |
264 ms |
212020 KB |
Output is correct |
10 |
Correct |
217 ms |
212144 KB |
Output is correct |
11 |
Correct |
160 ms |
211464 KB |
Output is correct |
12 |
Correct |
170 ms |
211496 KB |
Output is correct |
13 |
Correct |
243 ms |
211624 KB |
Output is correct |
14 |
Correct |
216 ms |
211516 KB |
Output is correct |
15 |
Correct |
176 ms |
211268 KB |
Output is correct |
16 |
Correct |
172 ms |
211264 KB |
Output is correct |
17 |
Correct |
197 ms |
211136 KB |
Output is correct |
18 |
Correct |
218 ms |
211528 KB |
Output is correct |
19 |
Correct |
272 ms |
211756 KB |
Output is correct |
20 |
Correct |
205 ms |
211528 KB |
Output is correct |
21 |
Correct |
4 ms |
5836 KB |
Output is correct |
22 |
Correct |
168 ms |
211704 KB |
Output is correct |
23 |
Correct |
251 ms |
211932 KB |
Output is correct |
24 |
Correct |
167 ms |
211388 KB |
Output is correct |
25 |
Correct |
161 ms |
211496 KB |
Output is correct |
26 |
Correct |
238 ms |
211580 KB |
Output is correct |
27 |
Correct |
192 ms |
211260 KB |
Output is correct |
28 |
Correct |
212 ms |
211436 KB |
Output is correct |
29 |
Correct |
269 ms |
211368 KB |
Output is correct |
30 |
Correct |
194 ms |
211524 KB |
Output is correct |
31 |
Correct |
280 ms |
211528 KB |
Output is correct |
32 |
Correct |
148 ms |
210864 KB |
Output is correct |
33 |
Correct |
224 ms |
212012 KB |
Output is correct |
34 |
Correct |
176 ms |
211388 KB |
Output is correct |
35 |
Correct |
173 ms |
211380 KB |
Output is correct |
36 |
Correct |
242 ms |
211768 KB |
Output is correct |
37 |
Correct |
202 ms |
211508 KB |
Output is correct |
38 |
Correct |
197 ms |
211264 KB |
Output is correct |
39 |
Correct |
313 ms |
211396 KB |
Output is correct |
40 |
Correct |
1006 ms |
211440 KB |
Output is correct |
41 |
Correct |
1262 ms |
211364 KB |
Output is correct |
42 |
Correct |
1405 ms |
211452 KB |
Output is correct |
43 |
Correct |
1 ms |
1612 KB |
Output is correct |
44 |
Correct |
4 ms |
5852 KB |
Output is correct |
45 |
Correct |
1284 ms |
1675376 KB |
Output is correct |
46 |
Correct |
1065 ms |
1670928 KB |
Output is correct |
47 |
Correct |
1055 ms |
1671224 KB |
Output is correct |
48 |
Correct |
1150 ms |
1673200 KB |
Output is correct |
49 |
Correct |
1430 ms |
1675384 KB |
Output is correct |
50 |
Correct |
1107 ms |
1672924 KB |
Output is correct |
51 |
Correct |
1048 ms |
1673228 KB |
Output is correct |
52 |
Correct |
972 ms |
1671124 KB |
Output is correct |
53 |
Correct |
1715 ms |
1671876 KB |
Output is correct |
54 |
Correct |
2179 ms |
1672980 KB |
Output is correct |
55 |
Correct |
2467 ms |
1671868 KB |
Output is correct |
56 |
Correct |
3573 ms |
1672548 KB |
Output is correct |
57 |
Correct |
2564 ms |
1672708 KB |
Output is correct |
58 |
Correct |
2850 ms |
1672828 KB |
Output is correct |
59 |
Correct |
2465 ms |
1672844 KB |
Output is correct |
60 |
Correct |
3809 ms |
1672116 KB |
Output is correct |
61 |
Correct |
3701 ms |
1672048 KB |
Output is correct |