#include "dungeons.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n;
vector<int> s, p, w, l, ds;
vector<vector<vector<ll>>> v;
void init(int N, vector<int> S, vector<int> P, vector<int> W, vector<int> L){
n = N;
s = S;
p = P;
w = W;
l = L;
s.push_back(0);
p.push_back(0);
w.push_back(n);
l.push_back(n);
v.resize(n+1, vector<vector<ll>>(30));
for (int i=0; i<30; i++){
for (int j=0; j<=n; j++){
if (i == 0) v[j][i] = {w[j], s[j], s[j]};
else {
v[j][i].push_back(v[v[j][i-1][0]][i-1][0]);
v[j][i].push_back(v[j][i-1][1] + v[v[j][i-1][0]][i-1][1]);
v[j][i].push_back(max(v[j][i-1][2], v[v[j][i-1][0]][i-1][2]-v[j][i-1][1]));
}
}
}
return;
}
ll simulate(int x, int z){
ll y = z;
while (x != n){
int i = 0;
while (v[x][i][2] <= y){
i++;
if (v[x][i-1][0] == n) break;
}
if (i == 0){
y += p[x];
x = l[x];
}
else {
y += v[x][i-1][1];
x = v[x][i-1][0];
}
}
return y;
}
