//GRT_2018
#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second
//mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
using namespace std;
using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;
const int nax = 50 * 1000 + 10, LOG = 25;
const ll INF = 1e18;
int n;
pair<int, ll>jp[nax][LOG][LOG];
ll lim[nax][LOG][LOG];
vi s, p, w, l;
void init(int N, vi _s, vi _p, vi _w, vi _l) {
n = N;
s = _s, w = _w, p = _p, l = _l;
s.PB(n);
for(int j = 0; j < LOG; ++j) {
for(int i = 0; i < n; ++i) {
int num = (1 << j);
if(num >= s[i]) {
jp[i][j][0] = {w[i], s[i]};
lim[i][j][0] = INF;
} else {
jp[i][j][0] = {l[i], p[i]};
lim[i][j][0] = s[i];
}
}
jp[n][j][0] = {n, 0};
lim[n][j][0] = INF;
}
for(int k = 1; k < LOG; ++k) {
for(int j = LOG - 1; j >= 0; --j) {
for(int i = 0; i < n; ++i) {
auto [id, sum] = jp[i][j][k - 1];
lim[i][j][k] = min(lim[i][j][k - 1], lim[id][j][k - 1] - sum);
jp[i][j][k] = {jp[id][j][k - 1].ST, sum + jp[id][j][k - 1].ND};
}
jp[n][j][k] = {n, 0};
lim[n][j][k] = INF;
}
}
}
ll simulate(int x, int zz) {
int inf = 10'000'000;
ll z = zz;
while(x != n) {
int bit = LOG - 1;
if(z < inf) {
bit = 31 - __builtin_clz(z);
}
for(int i = LOG - 1; i >= 0; --i) {
if(z < lim[x][bit][i]) {
z += jp[x][bit][i].ND;
x = jp[x][bit][i].ST;
}
}
// cerr << x << " " << z << "\n";
if(x == n) {
return z;
}
if(z >= s[x]) {
z += s[x];
x = w[x];
} else {
z += p[x];
x = l[x];
}
}
return z;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
436 KB |
Output is correct |
3 |
Correct |
46 ms |
29808 KB |
Output is correct |
4 |
Correct |
1444 ms |
737032 KB |
Output is correct |
5 |
Correct |
44 ms |
29900 KB |
Output is correct |
6 |
Correct |
1427 ms |
737028 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
15060 KB |
Output is correct |
2 |
Runtime error |
779 ms |
741292 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
15060 KB |
Output is correct |
2 |
Correct |
1605 ms |
737568 KB |
Output is correct |
3 |
Correct |
1462 ms |
737580 KB |
Output is correct |
4 |
Correct |
1374 ms |
737576 KB |
Output is correct |
5 |
Correct |
1357 ms |
737568 KB |
Output is correct |
6 |
Correct |
1502 ms |
737632 KB |
Output is correct |
7 |
Correct |
1533 ms |
737564 KB |
Output is correct |
8 |
Correct |
1374 ms |
737532 KB |
Output is correct |
9 |
Correct |
1458 ms |
737324 KB |
Output is correct |
10 |
Correct |
1435 ms |
737568 KB |
Output is correct |
11 |
Correct |
1678 ms |
737576 KB |
Output is correct |
12 |
Correct |
2069 ms |
737576 KB |
Output is correct |
13 |
Correct |
1727 ms |
738568 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
15060 KB |
Output is correct |
2 |
Correct |
1605 ms |
737568 KB |
Output is correct |
3 |
Correct |
1462 ms |
737580 KB |
Output is correct |
4 |
Correct |
1374 ms |
737576 KB |
Output is correct |
5 |
Correct |
1357 ms |
737568 KB |
Output is correct |
6 |
Correct |
1502 ms |
737632 KB |
Output is correct |
7 |
Correct |
1533 ms |
737564 KB |
Output is correct |
8 |
Correct |
1374 ms |
737532 KB |
Output is correct |
9 |
Correct |
1458 ms |
737324 KB |
Output is correct |
10 |
Correct |
1435 ms |
737568 KB |
Output is correct |
11 |
Correct |
1678 ms |
737576 KB |
Output is correct |
12 |
Correct |
2069 ms |
737576 KB |
Output is correct |
13 |
Correct |
1727 ms |
738568 KB |
Output is correct |
14 |
Correct |
17 ms |
15096 KB |
Output is correct |
15 |
Correct |
1471 ms |
738700 KB |
Output is correct |
16 |
Correct |
1554 ms |
738940 KB |
Output is correct |
17 |
Correct |
1443 ms |
738420 KB |
Output is correct |
18 |
Correct |
1495 ms |
738440 KB |
Output is correct |
19 |
Correct |
1642 ms |
738572 KB |
Output is correct |
20 |
Correct |
1576 ms |
738312 KB |
Output is correct |
21 |
Correct |
1589 ms |
738448 KB |
Output is correct |
22 |
Correct |
1542 ms |
738604 KB |
Output is correct |
23 |
Correct |
1849 ms |
738568 KB |
Output is correct |
24 |
Correct |
2531 ms |
738576 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
15060 KB |
Output is correct |
2 |
Correct |
1605 ms |
737568 KB |
Output is correct |
3 |
Correct |
1462 ms |
737580 KB |
Output is correct |
4 |
Correct |
1374 ms |
737576 KB |
Output is correct |
5 |
Correct |
1357 ms |
737568 KB |
Output is correct |
6 |
Correct |
1502 ms |
737632 KB |
Output is correct |
7 |
Correct |
1533 ms |
737564 KB |
Output is correct |
8 |
Correct |
1374 ms |
737532 KB |
Output is correct |
9 |
Correct |
1458 ms |
737324 KB |
Output is correct |
10 |
Correct |
1435 ms |
737568 KB |
Output is correct |
11 |
Correct |
1678 ms |
737576 KB |
Output is correct |
12 |
Correct |
2069 ms |
737576 KB |
Output is correct |
13 |
Correct |
1727 ms |
738568 KB |
Output is correct |
14 |
Correct |
17 ms |
15096 KB |
Output is correct |
15 |
Correct |
1471 ms |
738700 KB |
Output is correct |
16 |
Correct |
1554 ms |
738940 KB |
Output is correct |
17 |
Correct |
1443 ms |
738420 KB |
Output is correct |
18 |
Correct |
1495 ms |
738440 KB |
Output is correct |
19 |
Correct |
1642 ms |
738572 KB |
Output is correct |
20 |
Correct |
1576 ms |
738312 KB |
Output is correct |
21 |
Correct |
1589 ms |
738448 KB |
Output is correct |
22 |
Correct |
1542 ms |
738604 KB |
Output is correct |
23 |
Correct |
1849 ms |
738568 KB |
Output is correct |
24 |
Correct |
2531 ms |
738576 KB |
Output is correct |
25 |
Correct |
1805 ms |
737892 KB |
Output is correct |
26 |
Correct |
1868 ms |
738940 KB |
Output is correct |
27 |
Correct |
1657 ms |
738312 KB |
Output is correct |
28 |
Correct |
1733 ms |
738424 KB |
Output is correct |
29 |
Correct |
1850 ms |
738824 KB |
Output is correct |
30 |
Correct |
2060 ms |
738572 KB |
Output is correct |
31 |
Correct |
1863 ms |
738320 KB |
Output is correct |
32 |
Correct |
2280 ms |
738444 KB |
Output is correct |
33 |
Correct |
2577 ms |
738272 KB |
Output is correct |
34 |
Correct |
2737 ms |
738140 KB |
Output is correct |
35 |
Correct |
1920 ms |
738440 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
15060 KB |
Output is correct |
2 |
Runtime error |
779 ms |
741292 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |