This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 = 50010;
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 = 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) {
pl edge;
if (s[i] > SN) edge = {p[i], l[i]};
else edge = {s[i], w[i]};
par[i][0] = edge.K;
lift[i][0] = {edge.V, edge.V};
}
F(i, 0, L) lift[n][i] = {1e18, 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;
auto iterate1 = [&]{
if (z >= s[x]) z += s[x], x = w[x];
else z += p[x], x = l[x];
};
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
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.
FD(l, L-1, -1) {
const auto &[thresh, sm] = lift[x][l];
if (z < thresh) {
x = par[x][l];
z += sm;
// cout << "Jumped " << l << endl;
}
}
if (x == n) return z;
// cout << "WTF " << x << " " << z << " " << s[x] << endl;
// assert(s[x] > SN and z >= s[x]);
iterate1();
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |