#include <bits/stdc++.h> using namespace std; #include "dungeons.h" #define int long long vector<vector<tuple<int,int,int>>> lose,win; vector<int> skip; int m; void init(signed n,vector<signed> s,vector<signed> p,vector<signed> w,vector<signed> l){ m = n; lose = vector(n+1,vector<tuple<int,int,int>>(24)); for (int i(0);i < n;++i) lose[i][0] = make_tuple(l[i],s[i],p[i]); lose[n][0] = make_tuple(n,0,0); for (int k(1);k < 24;++k) for (int i(0);i <= n;++i){ auto [a,b,c] = lose[i][k-1]; auto [d,e,f] = lose[a][k-1]; lose[i][k] = make_tuple(d,min(b,e-c),c+f); } win = vector(n+1,vector<tuple<int,int,int>>(24)); for (int i(0);i < n;++i) win[i][0] = make_tuple(w[i],s[i],s[i]); win[n][0] = make_tuple(n,1e18,0); for (int k(1);k < 24;++k) for (int i(0);i <= n;++i){ auto [a,b,c] = win[i][k-1]; auto [d,e,f] = win[a][k-1]; win[i][k] = make_tuple(d,max(b,e-c),c+f); } skip = vector<int>(n+1); for (int i(n-1);i > -1;--i) skip[i] = skip[w[i]]+s[i]; } int simulate(signed x,signed y){ int z = y,t = 0; while(x!=m&&z<1e7){ if (get<1>(win[x][0])>z){ for (int l(23);l > -1;--l) if (get<1>(lose[x][l])>z){ z += get<2>(lose[x][l]),x = get<0>(lose[x][l]); } } else { ++t; for (int l(23);l > -1;--l) if (get<1>(win[x][l])<=z){ z += get<2>(win[x][l]),x = get<0>(win[x][l]); } } assert(t<6); } return z+skip[x]; }