#include<iostream>
#include<algorithm>
#include <vector>
using namespace std;
const int MAX_N=4e5+5;
const int LOG=19;
const long long INF=(1LL<<62);
vector<int>wg[MAX_N];
vector<int>lg[MAX_N];
int _s[MAX_N];
int _p[MAX_N];
int _w[MAX_N];
int _l[MAX_N];
int _n;
int wparent[MAX_N][LOG];
int wdep[MAX_N];
long long wdepth[MAX_N];
long long wmax[MAX_N][LOG];
void wdfs(int u)
{
for(int j=1;j<LOG;j++)
{
wparent[u][j]=wparent[wparent[u][j-1]][j-1];
wmax[u][j]=max(wmax[u][j-1],wmax[wparent[u][j-1]][j-1]);
}
for(int v:wg[u])
{
wdep[v]=wdep[u]+1;
wdepth[v]=wdepth[u]+_s[v];
wparent[v][0]=u;
wmax[v][0]=_s[v]+wdepth[v];
wdfs(v);
}
}
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=1;i<=_n;i++)
{
W[i-1]++;L[i-1]++;
_s[i]=S[i-1];
_p[i]=P[i-1];
_w[i]=W[i-1];
_l[i]=L[i-1];
wg[_w[i]].push_back(i);
lg[_l[i]].push_back(i);
}
wdfs(_n+1);
}
void firstlose(int&x,long long&cur)
{
for(int j=LOG-1;j>=0;j--)
{
if(wdep[x]-(1<<j)<0)continue;
if(wmax[x][j]<=cur+wdepth[x])
{
cur+=wdepth[x];
x=wparent[x][j];
cur-=wdepth[x];
}
}
if(x!=_n+1)
{
if(cur>=_s[x])
{
cur+=_s[x];
x=_w[x];
}
//else while(1);
}
}
long long simulate(int x, int z)
{
long long cur=z;
x++;
while(x!=_n+1)
{
if(cur<_s[x])
{
cur+=_p[x];
x=_l[x];
}
else
{
//cur+=_s[x];
//x=_w[x];
firstlose(x,cur);
}
}
return cur;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |