// Be Name Khoda //
#pragma GCC target("avx2")
#pragma GCC optimize("unroll-loops,O3")
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
#define MAX(x, y) ((x) > (y) ? (x) : (y))
#define MIN(x, y) ((x) < (y) ? (x) : (y))
#define debug(x) cerr << "(" << (#x) << "): " << (x) << endl;
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef long long ll;
const int maxn5 = 4e5 + 5;//4e2 + 5;
const int lgr = 25;
const int lgl = 13;
int n, par[lgr - lgl + 1][lgr][maxn5];
int s[maxn5], p[maxn5], w[maxn5], l[maxn5];
ll val[lgr - lgl][lgr][maxn5];
int mn[lgr - lgl][lgr][maxn5];
int get_lev(ll x){
return 63 - __builtin_clzll(x);
}
void init(int nn, std::vector<int> ss, std::vector<int> pp, std::vector<int> ww, std::vector<int> ll) {
n = nn;
for(int i = 0; i < n; i++){
s[i] = ss[i];
p[i] = pp[i];
w[i] = ww[i];
l[i] = ll[i];
}
memset(par, -1, sizeof par);
for(int x = 0; x < lgr - lgl; x++){
for(int i = 0; i < n; i++){
int re = ((1 << (x + lgl)) >= s[i]);
par[x][0][i] = re ? w[i] : l[i];
val[x][0][i] = re ? s[i] : p[i];
mn[x][0][i] = re ? -1 : s[i];
}
for(int k = 1; k < lgr; k++)
for(int i = 0; i < n; i++) if(par[x][k - 1][i] != -1){
int v = par[x][k - 1][i];
par[x][k][i] = par[x][k - 1][v];
val[x][k][i] = val[x][k - 1][i] + val[x][k - 1][v];
mn[x][k][i] = mn[x][k - 1][i];
if(mn[x][k - 1][v] != -1 && (mn[x][k - 1][i] == -1 || mn[x][k - 1][v] - val[x][k - 1][i] < mn[x][k][i]))
mn[x][k][i] = max(0ll, mn[x][k - 1][v] - val[x][k - 1][i]);
}
}
return;
}
long long simulate(int x, int zz) {
ll ret = zz;
while(ret < (1 << lgl) && x < n){
bool re = ret >= s[x];
ret += (re ? s[x] : p[x]);
x = (re ? w[x] : l[x]);
}
int last = -1;
while(x < n){
int lev = get_lev(ret);
lev = min(lev, lgr - 1);
if(lev < lgr - 1 && lev == last && false)
exit(0);
last = lev;
//debug("*******");
//debug(lev);
//debug(x);
//debug(ret);
lev -= lgl;
for(int i = lgr - 1; i >= 0; i--){
//debug(i);
//debug(x);
//debug(ret);
//debug(mn[lev][i][x]);
//debug(par[lev][i][x]);
if(par[lev][i][x] != -1 && (mn[lev][i][x] == -1 || mn[lev][i][x] > ret)){
ret += val[lev][i][x];
x = par[lev][i][x];
}
}
if(x == n)
return ret;
//debug("here");
//debug(x);
//debug(ret);
//debug(s[x]);
//debug(mn[lev][0][x]);
//debug(w[x]);
//debug(l[x]);
if(s[x] <= (1 << (lev + lgl)))
return -1;
bool re = ret >= s[x];
if(!re && false)
exit(0);
ret += (re ? s[x] : p[x]);
x = (re ? w[x] : l[x]);
}
return ret;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
147 ms |
509716 KB |
Output is correct |
2 |
Correct |
150 ms |
510104 KB |
Output is correct |
3 |
Correct |
149 ms |
511868 KB |
Output is correct |
4 |
Correct |
190 ms |
555556 KB |
Output is correct |
5 |
Correct |
154 ms |
512364 KB |
Output is correct |
6 |
Correct |
240 ms |
565972 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
158 ms |
516712 KB |
Output is correct |
2 |
Correct |
1426 ms |
1904996 KB |
Output is correct |
3 |
Correct |
1179 ms |
1878508 KB |
Output is correct |
4 |
Correct |
957 ms |
1790144 KB |
Output is correct |
5 |
Correct |
979 ms |
1491636 KB |
Output is correct |
6 |
Correct |
1287 ms |
1905028 KB |
Output is correct |
7 |
Correct |
1843 ms |
1908040 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
174 ms |
515648 KB |
Output is correct |
2 |
Correct |
284 ms |
659472 KB |
Output is correct |
3 |
Correct |
304 ms |
682204 KB |
Output is correct |
4 |
Correct |
245 ms |
626184 KB |
Output is correct |
5 |
Correct |
248 ms |
621432 KB |
Output is correct |
6 |
Correct |
342 ms |
658744 KB |
Output is correct |
7 |
Correct |
907 ms |
670156 KB |
Output is correct |
8 |
Correct |
336 ms |
625988 KB |
Output is correct |
9 |
Correct |
219 ms |
555376 KB |
Output is correct |
10 |
Correct |
522 ms |
625976 KB |
Output is correct |
11 |
Correct |
3589 ms |
626904 KB |
Output is correct |
12 |
Correct |
3957 ms |
684028 KB |
Output is correct |
13 |
Correct |
1474 ms |
679328 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
174 ms |
515648 KB |
Output is correct |
2 |
Correct |
284 ms |
659472 KB |
Output is correct |
3 |
Correct |
304 ms |
682204 KB |
Output is correct |
4 |
Correct |
245 ms |
626184 KB |
Output is correct |
5 |
Correct |
248 ms |
621432 KB |
Output is correct |
6 |
Correct |
342 ms |
658744 KB |
Output is correct |
7 |
Correct |
907 ms |
670156 KB |
Output is correct |
8 |
Correct |
336 ms |
625988 KB |
Output is correct |
9 |
Correct |
219 ms |
555376 KB |
Output is correct |
10 |
Correct |
522 ms |
625976 KB |
Output is correct |
11 |
Correct |
3589 ms |
626904 KB |
Output is correct |
12 |
Correct |
3957 ms |
684028 KB |
Output is correct |
13 |
Correct |
1474 ms |
679328 KB |
Output is correct |
14 |
Correct |
210 ms |
516624 KB |
Output is correct |
15 |
Correct |
359 ms |
681656 KB |
Output is correct |
16 |
Correct |
374 ms |
670164 KB |
Output is correct |
17 |
Correct |
341 ms |
668420 KB |
Output is correct |
18 |
Correct |
350 ms |
680736 KB |
Output is correct |
19 |
Correct |
486 ms |
681848 KB |
Output is correct |
20 |
Correct |
392 ms |
669296 KB |
Output is correct |
21 |
Correct |
366 ms |
681116 KB |
Output is correct |
22 |
Correct |
1542 ms |
616248 KB |
Output is correct |
23 |
Correct |
3527 ms |
648012 KB |
Output is correct |
24 |
Correct |
1892 ms |
647936 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
174 ms |
515648 KB |
Output is correct |
2 |
Correct |
284 ms |
659472 KB |
Output is correct |
3 |
Correct |
304 ms |
682204 KB |
Output is correct |
4 |
Correct |
245 ms |
626184 KB |
Output is correct |
5 |
Correct |
248 ms |
621432 KB |
Output is correct |
6 |
Correct |
342 ms |
658744 KB |
Output is correct |
7 |
Correct |
907 ms |
670156 KB |
Output is correct |
8 |
Correct |
336 ms |
625988 KB |
Output is correct |
9 |
Correct |
219 ms |
555376 KB |
Output is correct |
10 |
Correct |
522 ms |
625976 KB |
Output is correct |
11 |
Correct |
3589 ms |
626904 KB |
Output is correct |
12 |
Correct |
3957 ms |
684028 KB |
Output is correct |
13 |
Correct |
1474 ms |
679328 KB |
Output is correct |
14 |
Correct |
210 ms |
516624 KB |
Output is correct |
15 |
Correct |
359 ms |
681656 KB |
Output is correct |
16 |
Correct |
374 ms |
670164 KB |
Output is correct |
17 |
Correct |
341 ms |
668420 KB |
Output is correct |
18 |
Correct |
350 ms |
680736 KB |
Output is correct |
19 |
Correct |
486 ms |
681848 KB |
Output is correct |
20 |
Correct |
392 ms |
669296 KB |
Output is correct |
21 |
Correct |
366 ms |
681116 KB |
Output is correct |
22 |
Correct |
1542 ms |
616248 KB |
Output is correct |
23 |
Correct |
3527 ms |
648012 KB |
Output is correct |
24 |
Correct |
1892 ms |
647936 KB |
Output is correct |
25 |
Correct |
331 ms |
671556 KB |
Output is correct |
26 |
Correct |
404 ms |
681712 KB |
Output is correct |
27 |
Correct |
375 ms |
681668 KB |
Output is correct |
28 |
Correct |
371 ms |
681632 KB |
Output is correct |
29 |
Correct |
413 ms |
681640 KB |
Output is correct |
30 |
Correct |
466 ms |
681948 KB |
Output is correct |
31 |
Correct |
481 ms |
681956 KB |
Output is correct |
32 |
Correct |
1300 ms |
639192 KB |
Output is correct |
33 |
Correct |
633 ms |
684364 KB |
Output is correct |
34 |
Correct |
2033 ms |
676376 KB |
Output is correct |
35 |
Correct |
521 ms |
684028 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
158 ms |
516712 KB |
Output is correct |
2 |
Correct |
1426 ms |
1904996 KB |
Output is correct |
3 |
Correct |
1179 ms |
1878508 KB |
Output is correct |
4 |
Correct |
957 ms |
1790144 KB |
Output is correct |
5 |
Correct |
979 ms |
1491636 KB |
Output is correct |
6 |
Correct |
1287 ms |
1905028 KB |
Output is correct |
7 |
Correct |
1843 ms |
1908040 KB |
Output is correct |
8 |
Correct |
174 ms |
515648 KB |
Output is correct |
9 |
Correct |
284 ms |
659472 KB |
Output is correct |
10 |
Correct |
304 ms |
682204 KB |
Output is correct |
11 |
Correct |
245 ms |
626184 KB |
Output is correct |
12 |
Correct |
248 ms |
621432 KB |
Output is correct |
13 |
Correct |
342 ms |
658744 KB |
Output is correct |
14 |
Correct |
907 ms |
670156 KB |
Output is correct |
15 |
Correct |
336 ms |
625988 KB |
Output is correct |
16 |
Correct |
219 ms |
555376 KB |
Output is correct |
17 |
Correct |
522 ms |
625976 KB |
Output is correct |
18 |
Correct |
3589 ms |
626904 KB |
Output is correct |
19 |
Correct |
3957 ms |
684028 KB |
Output is correct |
20 |
Correct |
1474 ms |
679328 KB |
Output is correct |
21 |
Correct |
210 ms |
516624 KB |
Output is correct |
22 |
Correct |
359 ms |
681656 KB |
Output is correct |
23 |
Correct |
374 ms |
670164 KB |
Output is correct |
24 |
Correct |
341 ms |
668420 KB |
Output is correct |
25 |
Correct |
350 ms |
680736 KB |
Output is correct |
26 |
Correct |
486 ms |
681848 KB |
Output is correct |
27 |
Correct |
392 ms |
669296 KB |
Output is correct |
28 |
Correct |
366 ms |
681116 KB |
Output is correct |
29 |
Correct |
1542 ms |
616248 KB |
Output is correct |
30 |
Correct |
3527 ms |
648012 KB |
Output is correct |
31 |
Correct |
1892 ms |
647936 KB |
Output is correct |
32 |
Correct |
331 ms |
671556 KB |
Output is correct |
33 |
Correct |
404 ms |
681712 KB |
Output is correct |
34 |
Correct |
375 ms |
681668 KB |
Output is correct |
35 |
Correct |
371 ms |
681632 KB |
Output is correct |
36 |
Correct |
413 ms |
681640 KB |
Output is correct |
37 |
Correct |
466 ms |
681948 KB |
Output is correct |
38 |
Correct |
481 ms |
681956 KB |
Output is correct |
39 |
Correct |
1300 ms |
639192 KB |
Output is correct |
40 |
Correct |
633 ms |
684364 KB |
Output is correct |
41 |
Correct |
2033 ms |
676376 KB |
Output is correct |
42 |
Correct |
521 ms |
684028 KB |
Output is correct |
43 |
Correct |
200 ms |
509672 KB |
Output is correct |
44 |
Correct |
205 ms |
516648 KB |
Output is correct |
45 |
Correct |
1345 ms |
1783472 KB |
Output is correct |
46 |
Correct |
1145 ms |
1760532 KB |
Output is correct |
47 |
Correct |
1152 ms |
1848704 KB |
Output is correct |
48 |
Correct |
1255 ms |
1905044 KB |
Output is correct |
49 |
Correct |
1399 ms |
1860092 KB |
Output is correct |
50 |
Correct |
1140 ms |
1914284 KB |
Output is correct |
51 |
Correct |
1086 ms |
1913048 KB |
Output is correct |
52 |
Correct |
1139 ms |
1879752 KB |
Output is correct |
53 |
Correct |
2997 ms |
1579120 KB |
Output is correct |
54 |
Correct |
1550 ms |
1893320 KB |
Output is correct |
55 |
Correct |
3180 ms |
1843004 KB |
Output is correct |
56 |
Correct |
1910 ms |
1890028 KB |
Output is correct |
57 |
Correct |
1879 ms |
1885724 KB |
Output is correct |
58 |
Correct |
2041 ms |
1885624 KB |
Output is correct |
59 |
Correct |
2555 ms |
1885668 KB |
Output is correct |
60 |
Correct |
2244 ms |
1907684 KB |
Output is correct |
61 |
Correct |
1616 ms |
1894272 KB |
Output is correct |