// #include <vector> #include <bits/stdc++.h> using namespace std; #define ll long long const int N=4e5+1,LG=24,PW=8,B=10; const ll inf=1e18; ll n,s[N],p[N],w[N],l[N]; ll nxt[PW][N][LG],th[PW][N][LG]; ll inc[PW][N][LG]; void init(int n2, std::vector<int> s1, std::vector<int> p1, std::vector<int> w1, std::vector<int> l1) { n=n2; for(int i=0;i<n;i++) { s[i]=s1[i]; p[i]=p1[i]; w[i]=w1[i]; l[i]=l1[i]; } s[n]=p[n]=0; w[n]=l[n]=n; for(int k=0;k<PW;k++) { ll pw=(ll)pow(B,k); // assume 2^k <= z < 2^(k+1) // for all si < 2^k we win for(int j=0;j<=n;j++) { if(s[j]<=pw) { nxt[k][j][0]=w[j]; inc[k][j][0]=s[j]; th[k][j][0]=inf; } else { nxt[k][j][0]=l[j]; inc[k][j][0]=p[j]; th[k][j][0]=s[j]; // if z>=th[j] then we could have won at stage } } for(int j=1;j<LG;j++) { for(int i=0;i<=n;i++) { nxt[k][i][j]=nxt[k][nxt[k][i][j-1]][j-1]; inc[k][i][j]=inc[k][i][j-1] + inc[k][nxt[k][i][j-1]][j-1]; th[k][i][j]=min((ll)th[k][i][j-1],th[k][nxt[k][i][j-1]][j-1] - inc[k][i][j-1]); } } } } long long simulate(int x1, int z1) { long long z=z1,x=x1; ll pw=1,lg=0; while(x!=n) { while((pw*B)<=z) { pw*=B; lg++; } lg=min(lg,7ll); for(int j=LG-1;j>=0;j--) { if(th[lg][x][j]>z) // we dont win { z+=inc[lg][x][j]; x=nxt[lg][x][j]; } } if(s[x]<=z) { z+=s[x]; x=w[x]; } else { z+=p[x]; x=l[x]; } } return z; }