#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx") // codeforces
#undef _GLIBCXX_DEBUG
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
const int BLOCK_1 = 500;
const int BLOCK_2 = 50000;
const int MAX_SKILL = 1.01e7;
const int U = 20;
const int inf = 1e9;
int n;
struct Link{
int to;
int gain;
};
struct Node{
Link win, loss;
int thresh;
};
struct Jump{
int to;
int max_valid;
ll gain;
};
vector<ll> win_gain;
vector<Node> g;
vector<vector<Jump> > jumps_1;
vector<vector<Jump> > jumps_2;
void init(int n_, vector<int> s, vector<int> p, vector<int> w, vector<int> l){
n = n_;
g.assign(n+1, Node{});
for(int i=0; i<n; ++i){
g[i] = Node{Link{w[i], s[i]}, Link{l[i], p[i]}, s[i]};
}
g[n] = Node{Link{n, 0}, Link{n, 0}, 0};
// compute win once we hit 1e7
win_gain.assign(n+1, 0);
for(int i=n-1; i>=0; --i){
win_gain[i] = win_gain[g[i].win.to] + g[i].win.gain;
}
auto compute_table = [&](auto &jumps, int BLOCK){
// assume we take BLOCK steps
// then build jump table
jumps.resize(U+1, vector<Jump>(n+1));
for(int i=0; i<=n; ++i){
if(g[i].thresh <= BLOCK){
jumps[0][i] = Jump{g[i].win.to, inf, g[i].win.gain};
} else {
jumps[0][i] = Jump{g[i].loss.to, g[i].thresh-1, g[i].loss.gain};
}
}
jumps[0][n].max_valid = 0;
for(int i=1; i<=U; ++i){
for(int j=0; j<=n; ++j){
auto &e = jumps[i-1][j];
const int k = e.to;
auto const&f = jumps[i-1][k];
jumps[i][j] = Jump{f.to, max<ll>(-1, min<ll>(e.max_valid, f.max_valid-e.gain)), e.gain+f.gain};
}
}
};
compute_table(jumps_1, BLOCK_1);
compute_table(jumps_2, BLOCK_2);
}
long long simulate(int x, int z) {
int u = x;
ll s = z;
auto do_single_step = [&](){
if(s >= g[u].thresh){
s += g[u].win.gain;
u = g[u].win.to;
} else {
s += g[u].loss.gain;
u = g[u].loss.to;
}
};
auto run_with_jumps = [&](auto const&jumps, int const SKILL_CAP){
while(u != n && s < SKILL_CAP){
int i = 0;
while(i >= 0){
auto &e = jumps[i][u];
if(s < e.max_valid){
s += e.gain;
u = e.to;
i = min(i+1, U);
} else --i;
}
do_single_step();
}
};
for(int it=0; it<BLOCK_1; ++it){
do_single_step();
}
assert(u == n || s >= BLOCK_1);
run_with_jumps(jumps_1, BLOCK_2);
run_with_jumps(jumps_2, MAX_SKILL);
s += win_gain[u];
return s;
}
