This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1e18;
const int maxn=(4e5)+10;
int n,hd,tl,q[maxn],lg[maxn*2];
struct Tree {
int a[maxn],in[maxn];
ll w[maxn],dep[maxn],p[maxn]; bool cyc[maxn],vis[maxn];
vector<int> son[maxn];
int fa[maxn][20]; ll mn[maxn][20];
void dfs(int u) {
for (int v : son[u]) if (!cyc[v]) {
dep[v]=dep[u]+p[v]; dfs(v);
}
}
int cnt,L[maxn],R[maxn],tot,bel[maxn];
ll all[maxn],pre[maxn*2],st[maxn*2][21];
int rem[maxn*2],pos[maxn];
ll query(int l,int r) {
int j=lg[r-l+1];
return min(st[l][j],st[r-(1<<j)+1][j]);
}
void build() {
for (int i=1;i<=n;i++) in[a[i]]++,son[a[i]].push_back(i),fa[i][0]=a[i];
//for (int i=1;i<=n;i++) printf("a[%d]=%d,w[%d]=%lld,p[%d]=%lld\n",i,a[i],i,w[i],i,p[i]);
hd=1,tl=0;
for (int i=1;i<=n;i++) if (!in[i]) q[++tl]=i;
while (hd<=tl) {
int x=q[hd]; hd++;
int y=a[x];
in[y]--; if (!in[y]) q[++tl]=y;
}
for (int i=1;i<=n;i++) if (in[i]) cyc[i]=1;//,printf("cyc=%d\n",i);
for (int i=1;i<=n;i++) if (cyc[i]) {
dfs(i); fa[i][0]=0;
if (!vis[i]) {
int x=i;
cnt++; L[cnt]=tot+1;
while (1) {
bel[x]=cnt; all[cnt]+=p[x]; vis[x]=1;
tot++; pos[x]=tot; rem[tot]=x;
x=a[x]; if (x==i) break;
}
R[cnt]=tot;
for (int j=L[cnt];j<=R[cnt];j++) rem[++tot]=rem[j];
R[cnt]=tot;
ll now=0;
for (int j=L[cnt];j<=R[cnt];j++) {
st[j][0]=w[rem[j]]-now;
pre[j]=now;
now+=p[rem[j]];
}
}
}
for (int i=1;i<=n;i++) mn[i][0]=dep[a[i]]+w[a[i]];
for (int i=1;i<=20;i++) for (int j=1;j+(1<<i)-1<=tot;j++)
st[j][i]=min(st[j][i-1],st[j+(1<<(i-1))][i-1]);
for (int i=1;i<=19;i++) for (int j=1;j<=n;j++)
fa[j][i]=fa[fa[j][i-1]][i-1],mn[j][i]=min(mn[fa[j][i-1]][i-1],mn[j][i-1]);
}
void solve(int &x,ll &now) {
// printf("x=%d,now=%lld\n",x,now);
if (now>=w[x]) return;
if (!cyc[x]) {
int y=x;
for (int i=19;i>=0;i--) if (fa[y][i]) {
if (now+dep[x]<mn[y][i]) y=fa[y][i];
}
if (!cyc[y]) y=fa[y][0];
now+=dep[x]-dep[y]; x=y;
//printf("y=%d\n",y);
if (now>=w[x]) return;
}
if (x==n) return;
// printf("%d\n",x);
ll mn=query(pos[x],R[bel[x]]);
ll bd=mn+pre[pos[x]]-now;
int rd; if (bd<=0) rd=0; else if (bd%all[bel[x]]==0) rd=bd/all[bel[x]]; else rd=bd/all[bel[x]]+1;
int y=pos[x]+1;
for (int i=19;i>=0;i--) if (y+(1<<i)-1<=R[bel[x]]) {
if (now-pre[pos[x]]+all[bel[x]]*rd<st[y][i]) y+=(1<<i);
}
now+=pre[y]-pre[pos[x]]+all[bel[x]]*rd;
x=rem[y];
}
} tr[3];
int s[maxn],w[maxn],p[maxn],nxt[maxn];
void init(int _n,vector<int> _s,vector<int> _p,vector<int> _w,vector<int> _l) {
n=_n;
for (int i=1;i<=n;i++) s[i]=_s[i-1],w[i]=_w[i-1]+1,p[i]=_p[i-1],nxt[i]=_l[i-1]+1;
w[n+1]=nxt[n+1]=n+1; n++;
// printf("MLE %d\n",sizeof(tr)/1024/1024);
for (int i=2;i<=n*2;i++) lg[i]=lg[i>>1]+1;
// puts("OK");
for (int i=0;i<3;i++) {
for (int j=1;j<=n;j++) {
if (j==n||(s[j]>>(i*9))) tr[i].a[j]=nxt[j],tr[i].w[j]=s[j],tr[i].p[j]=p[j];
else tr[i].a[j]=w[j],tr[i].w[j]=INF/10,tr[i].p[j]=s[j];
}
tr[i].build();
}
// puts("OK");
}
ll simulate(int x, int z) {
x++; ll now=z;
for (int i=0;i<3;i++) {
while (now<(1LL<<(i*9+9))) {
tr[i].solve(x,now);
// printf("%d %d %lld\n",i,x,now);
assert(x);
if (x==n) break;
now+=s[x]; x=w[x]; if (x==n) break;
}
}
return now;
}
# | 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... |