#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int N;
vector<int> S, P, W, L;
vector<int> win_dist;
vector<int> visited;
vector<int> cycle;
vector<vector<int>> inc;
vector<vector<int>> bl_node;
vector<vector<ll>> bl_dist;
vector<ll> cycle_length;
void binary_lifting(int index, ll total_dist, vector<int>& nodes, vector<ll>& dist)
{
int nt = 1;
const int sz = nodes.size();
while (nt <= sz)
{
bl_node[index].push_back(nodes[sz - nt]);
bl_dist[index].push_back(total_dist - dist[sz - nt]);
nt <<= 1;
}
nodes.push_back(index);
dist.push_back(total_dist);
for (auto node : inc[index])
{
binary_lifting(node, total_dist + P[node], nodes, dist);
}
nodes.pop_back();
dist.pop_back();
}
ll target;
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;
L.push_back(N);
P.push_back(0);
target = s[0];
// Find winning distance
win_dist = vector<int>(N+1);
for (int i = N - 1; i >= 0; i--)
win_dist[i] = win_dist[W[i]] + 1;
vector<int> inc_cnt(N+1);
for (int i = 0; i < N + 1; i++)
{
inc_cnt[L[i]]++;
}
queue<int> path_nodes;
for (int i = 0; i < N + 1; i++)
{
if (!inc_cnt[i])
path_nodes.push(i);
}
inc = vector<vector<int>>(N+1);
while (!path_nodes.empty())
{
int s = path_nodes.front();
path_nodes.pop();
inc[L[s]].push_back(s);
if (--inc_cnt[L[s]] == 0)
path_nodes.push(L[s]);
}
bl_node = vector<vector<int>>(N+1);
bl_dist = vector<vector<ll>>(N+1);
for (int i = 0; i < N + 1; i++)
{
if (!inc_cnt[i] || !inc[i].size()) continue;
vector<int> nodes;
vector<ll> dist;
binary_lifting(i, 0, nodes, dist);
}
cycle = vector<int>(N+1);
cycle_length = vector<ll>(N+1);
for (int i = 0; i < N+1; i++)
{
if (!inc_cnt[i] || cycle[i]) continue;
vector<int> nodes;
vector<ll> dist;
int current_node = L[i];
ll current_dist = P[i];
while (current_node != i)
{
nodes.push_back(current_node);
dist.push_back(current_dist);
current_dist += p[current_node];
current_node = L[current_node];
}
nodes.push_back(current_node);
dist.push_back(current_dist);
ll sub = 0; int cnt = 0;
const int sz = nodes.size();
while (!cycle[current_node])
{
cycle[current_node] = 1;
cycle_length[current_node] = current_dist;
int nt = 1;
while (nt <= sz)
{
bl_node[current_node].push_back(nodes[cnt + nt-1]);
bl_dist[current_node].push_back(dist[cnt + nt-1] - sub);
nt <<= 1;
}
if (dist.size())
{
dist.push_back(dist.back() + p[nodes.back()]);
nodes.push_back(L[nodes.back()]);
}
sub += P[current_node];
cnt++;
current_node = L[current_node];
}
}
// Debugging
/*for (int i = 0; i < N + 1; i++)
{
cerr << i << ": (" << (cycle[i] ? "cycle) " : "path) ") << cycle_length[i] << '\n';
if (!bl_node[i].size()) continue;
for (auto e : bl_node[i])
cerr << e << ' ';
cerr << '\n';
for (auto e : bl_dist[i])
cerr << e << ' ';
cerr << '\n';
}*/
}
ll strength;
ll simulate(int x, int z)
{
strength = z;
if (x == N)
return strength;
while (!cycle[x] && strength < target)
{
const int sz = bl_node[x].size();
for (int i = sz - 1; i >= 0; i--)
{
if (strength + bl_dist[x][i] >= target)
continue;
strength += bl_dist[x][i];
x = bl_node[x][i];
break;
}
if (strength + P[x] >= target)
{
strength += P[x];
x = L[x];
}
}
if (strength >= target)
return strength + win_dist[x] * target;
strength += cycle_length[x] * ((target - strength) / cycle_length[x]);
while (strength < target)
{
const int sz = bl_node[x].size();
for (int i = sz - 1; i >= 0; i--)
{
if (strength + bl_dist[x][i] >= target)
continue;
strength += bl_dist[x][i];
x = bl_node[x][i];
break;
}
if (strength + P[x] >= target)
{
strength += P[x];
x = L[x];
}
}
return strength + win_dist[x] * target;
}
