#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long ;
#define A(a) (a).begin(), (a).end()
using pl = pair<ll, ll>;
using vl = vector<ll>;
#define F(i, l, r) for (ll i = (l); i < (r); ++i)
#define FD(i, l, r) for (ll i = (l); i > (r); --i)
#define K first
#define V second
const ll NN = 5e4+10;
// const ll NN = 4e5+10;
// const ll SN = 0;
const ll SN = 3200;
ll n;
ll s[NN], p[NN], w[NN], l[NN];
// We need this, because this lets us win fast. Otherwise ,would take O(n) even when strength >> 1e7
pl ans[NN]; // {minimum strength needed to clear to root, bonus delta }
using T = pl;
const ll L = 26;
pl lift[NN][L];
ll par[NN][L];
constexpr ll INF = 1e18;
T f(T a, T b) {
T res;
res.K = min(a.K, b.K - a.V);
res.V = min(2*INF, a.V + b.V);
return res;
}
void init(int _n, vector<int> _s, vector<int> _p, vector<int> _w, vector<int> _l) {
n = _n;
copy(A(_s), s);
copy(A(_p), p);
copy(A(_w), w);
copy(A(_l), l);
// precomp ans
FD(i, n-1, -1) {
ans[i].K = max(s[i], ans[w[i]].K - s[i]);
ans[i].V = ans[w[i]].V + s[i];
}
F(i, 0, n) {
if (s[i] > SN) {
par[i][0] = l[i];
lift[i][0] = {s[i], p[i]};
} else {
// when strength > SN, we always win here, so fix these to be winning edge.
par[i][0] = w[i];
lift[i][1] = {s[i], s[i]};
}
}
F(i, 0, L) lift[n][i] = {-INF, 0};
F(l, 1, L) F(i, 0, n) {
par[i][l] = par[par[i][l-1]][l-1];
lift[i][l] = f(lift[i][l-1], lift[par[i][l-1]][l-1]);
}
// F(i, 0, n) {
// F(l, 0, L) cout << lift[i][l].K << " " << lift[i][l].V << " | ";
// cout << endl;
// }
}
long long simulate(int _x, int _z) {
ll x = _x, z = _z;
ll moves = 0;
auto iterate1 = [&]{
if (z >= s[x]) {
// cout << "ADDED UP " << s[x] << endl;
z += s[x], x = w[x];
}
else {
// cout << "ADDED DOWN " << p[x] << endl;
z += p[x], x = l[x];
}
++moves;
};
while (x != n and z <= SN) {
iterate1();
}
if (x == n) return z;
// TODO: implement some kind of bsearch dictating how far to go while taking
// only "losing" edges
// cout << "Currently: " << x << " " << z << endl;
while (1) {
if (ans[x].K <= z) return ans[x].V + z;
// cout << "Started with " << x << " " << z << endl;
// figure out where to jump, then update x and z. We are now at a winning node.
// if (0)
FD(l, L-1, -1) {
const auto &[thresh, sm] = lift[x][l];
// if (l == 1) {
// cout << "Why not jump here? " << endl;
// cout << thresh << " " << sm << " | " << z << endl;
// auto [a1, b1] = lift[0][0];
// auto [a2, b2] = lift[1][0];
// cout << a1 << " " << b1 << " " << a2 << " " << b2 << endl;
// }
// cout << z << " " << thresh << " " << sm << endl;
if (z < thresh ) {
x = par[x][l];
z += sm;
// cout << "Jumped " << l << endl;
moves += 1<<l;
}
}
// cout << "WTF U ON " << moves << endl;
if (x == n) return z;
// iterate1();
// cout << "WTF " << x << " " << z << " " << s[x] << endl;
// assert(s[x] > SN);
// assert(z >= s[x]);
iterate1();
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Output is correct |
2 |
Correct |
1 ms |
2396 KB |
Output is correct |
3 |
Correct |
3 ms |
6748 KB |
Output is correct |
4 |
Correct |
30 ms |
34692 KB |
Output is correct |
5 |
Correct |
3 ms |
6744 KB |
Output is correct |
6 |
Correct |
28 ms |
34900 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
6748 KB |
Output is correct |
2 |
Runtime error |
149 ms |
28216 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
6744 KB |
Output is correct |
2 |
Correct |
58 ms |
35408 KB |
Output is correct |
3 |
Correct |
48 ms |
35548 KB |
Output is correct |
4 |
Correct |
42 ms |
35656 KB |
Output is correct |
5 |
Correct |
41 ms |
35564 KB |
Output is correct |
6 |
Correct |
70 ms |
35672 KB |
Output is correct |
7 |
Correct |
240 ms |
35560 KB |
Output is correct |
8 |
Correct |
74 ms |
35624 KB |
Output is correct |
9 |
Correct |
41 ms |
35672 KB |
Output is correct |
10 |
Correct |
106 ms |
35676 KB |
Output is correct |
11 |
Correct |
1568 ms |
35672 KB |
Output is correct |
12 |
Correct |
1649 ms |
35468 KB |
Output is correct |
13 |
Correct |
402 ms |
35676 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
6744 KB |
Output is correct |
2 |
Correct |
58 ms |
35408 KB |
Output is correct |
3 |
Correct |
48 ms |
35548 KB |
Output is correct |
4 |
Correct |
42 ms |
35656 KB |
Output is correct |
5 |
Correct |
41 ms |
35564 KB |
Output is correct |
6 |
Correct |
70 ms |
35672 KB |
Output is correct |
7 |
Correct |
240 ms |
35560 KB |
Output is correct |
8 |
Correct |
74 ms |
35624 KB |
Output is correct |
9 |
Correct |
41 ms |
35672 KB |
Output is correct |
10 |
Correct |
106 ms |
35676 KB |
Output is correct |
11 |
Correct |
1568 ms |
35672 KB |
Output is correct |
12 |
Correct |
1649 ms |
35468 KB |
Output is correct |
13 |
Correct |
402 ms |
35676 KB |
Output is correct |
14 |
Correct |
2 ms |
6744 KB |
Output is correct |
15 |
Correct |
672 ms |
35560 KB |
Output is correct |
16 |
Correct |
46 ms |
35676 KB |
Output is correct |
17 |
Correct |
42 ms |
35676 KB |
Output is correct |
18 |
Correct |
1992 ms |
35672 KB |
Output is correct |
19 |
Correct |
64 ms |
35672 KB |
Output is correct |
20 |
Correct |
161 ms |
35684 KB |
Output is correct |
21 |
Correct |
1403 ms |
35672 KB |
Output is correct |
22 |
Execution timed out |
7092 ms |
35676 KB |
Time limit exceeded |
23 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
6744 KB |
Output is correct |
2 |
Correct |
58 ms |
35408 KB |
Output is correct |
3 |
Correct |
48 ms |
35548 KB |
Output is correct |
4 |
Correct |
42 ms |
35656 KB |
Output is correct |
5 |
Correct |
41 ms |
35564 KB |
Output is correct |
6 |
Correct |
70 ms |
35672 KB |
Output is correct |
7 |
Correct |
240 ms |
35560 KB |
Output is correct |
8 |
Correct |
74 ms |
35624 KB |
Output is correct |
9 |
Correct |
41 ms |
35672 KB |
Output is correct |
10 |
Correct |
106 ms |
35676 KB |
Output is correct |
11 |
Correct |
1568 ms |
35672 KB |
Output is correct |
12 |
Correct |
1649 ms |
35468 KB |
Output is correct |
13 |
Correct |
402 ms |
35676 KB |
Output is correct |
14 |
Correct |
2 ms |
6744 KB |
Output is correct |
15 |
Correct |
672 ms |
35560 KB |
Output is correct |
16 |
Correct |
46 ms |
35676 KB |
Output is correct |
17 |
Correct |
42 ms |
35676 KB |
Output is correct |
18 |
Correct |
1992 ms |
35672 KB |
Output is correct |
19 |
Correct |
64 ms |
35672 KB |
Output is correct |
20 |
Correct |
161 ms |
35684 KB |
Output is correct |
21 |
Correct |
1403 ms |
35672 KB |
Output is correct |
22 |
Execution timed out |
7092 ms |
35676 KB |
Time limit exceeded |
23 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
6748 KB |
Output is correct |
2 |
Runtime error |
149 ms |
28216 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |