#include "dungeons.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
constexpr int maxn = 4e5+10, logn = 5;
constexpr long long inf = 1e15L;
struct FunctionalGraph {
int n;
int p[maxn], f[maxn]; // s[i] == força necessaria para matar i, p[i] == peso da aresta saindo de i, f[i] == aresta saindo de i
long long s[maxn];
int tp[maxn]; // se tá vivo ou se tá morto, definido junto com o s[i]
void add_edge(int i, int x, int v) { f[i] = x, p[i] = v; }
void set_s(int i, long long st) { s[i] = st; tp[i] = st != inf; }
bool in_cycle[maxn];
int mark[maxn], prox_bom[maxn];
long long dist_bom[maxn];
// int prox_cycle[maxn];
// long long dist_cycle[maxn];
void dfs(int u) {
mark[u] = 1;
if(mark[f[u]] == 1) {
int fim = u; u = f[u]; in_cycle[fim] = 1;
while(u != fim) in_cycle[u] = 1, u = f[u];
}
else if(!mark[f[u]]) dfs(f[u]);
mark[u] = 2;
}
void dfs_cycle(int u, int fim) { // tenho q comecar em f[bom], com bom estando no ciclo
mark[u] = 1;
if(u != fim) dfs_cycle(f[u], fim);
dist_bom[u] = tp[u] ? 0 : dist_bom[f[u]] + p[u];
prox_bom[u] = tp[u] ? u : prox_bom[f[u]];
}
void dfs2(int u) {
mark[u] = 1;
if(!mark[f[u]]) dfs2(f[u]);
dist_bom[u] = tp[u] ? 0 : dist_bom[f[u]] + p[u];
prox_bom[u] = tp[u] ? u : prox_bom[f[u]];
}
void build(int _n, int debugar = 0) { // n é a quantidade de vertices desse grafo, n é sempre igual ao n geral, não é um grafo compresso
n = _n;
f[n] = n;
s[n] = 0;
p[n] = 0;
tp[n] = 1;
in_cycle[n] = 1;
memset(prox_bom, -1, sizeof prox_bom);
for(int i = 0; i <= n; i++)
if(!mark[i]) dfs(i);
memset(mark, 0, sizeof mark);
for(int i = 0; i <= n; i++)
if(!mark[i] && in_cycle[i] && tp[i]) dfs_cycle(f[i], i);
for(int i = 0; i <= n; i++)
if(!mark[i]) dfs2(i);
if(debugar) {
for(int i = 0; i <= n; i++) {
printf("%d == \n", i);
printf("%lld %d %d\n", s[i], p[i], f[i]);
// printf("(%d %lld) ", prox_bom[i], dist_bom[i]);
puts("\n");
}
}
}
void go(int& x, long long& val) {
val += dist_bom[x];
x = prox_bom[x];
// printf("%d %lld\n\n", x, val);
if(val >= s[x]) return; // na subtask s[i] == p[i] isso só vai ser falso uma vez então essa recursão é O(1)
val += p[x];
x = f[x];
// printf("%d %lld\n", x, val);
go(x, val);
}
} graph[logn];
int s[maxn], p[maxn], w[maxn], l[maxn], n;
void init(int N, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L) {
n = N;
for(int i = 0; i < n; i++)
s[i] = S[i];
for(int i = 0; i < n; i++)
p[i] = P[i];
for(int i = 0; i < n; i++)
w[i] = W[i];
for(int i = 0; i < n; i++)
l[i] = L[i];
for(int lg = 0; lg < logn; lg++) {
int lim = 1<<lg;
for(int i = 0; i < n; i++) {
if(s[i] <= lim) {
graph[lg].add_edge(i, w[i], s[i]);
graph[lg].set_s(i, inf); // já ta morto
} else {
graph[lg].add_edge(i, l[i], p[i]);
graph[lg].set_s(i, s[i]);
}
}
graph[lg].build(n);
}
return;
}
long long simulate(int x, int z) {
long long val = z;
// printf("%d %lld\n", x, val);
for(int lg = 0; lg < logn; lg++) {
graph[lg].go(x, val);
// printf("%d %lld\n", x, val);
}
// puts("");
return val;
// return 0;
}
