#include <bits/stdc++.h> using namespace std; #include "dungeons.h" #define int long long vector<vector<tuple<int,int,int>>> lose; vector<pair<int,int>> 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>>(19)); 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 < 19;++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<pair<int,int>>(n+1,make_pair(n,0)); for (int i(0);i < n;++i) win[i] = make_pair(w[i],s[i]); skip = vector<int>(n+1); for (int i(n-1);i > -1;--i) skip[i] = skip[win[i].first]+win[i].second; } int simulate(signed x,signed y){ int z = y; while(x!=m&&z<1e7){ if (win[x].second>z){ for (int l(18);l > -1;--l) if (get<1>(lose[x][l])>z){ z += get<2>(lose[x][l]),x = get<0>(lose[x][l]); } } else z += win[x].second,x = win[x].first; } return z+skip[x]; }