제출 #439661

#제출 시각아이디문제언어결과실행 시간메모리
439661haojiandan던전 (IOI21_dungeons)C++17
0 / 100
84 ms69188 KiB
#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]; int sz[maxn],dfn[maxn],idx,top[maxn],FA[maxn],mxson[maxn]; ll mn[maxn],D[maxn]; int bk[maxn]; 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]; void dfs(int u) { sz[u]=1; for (int v : son[u]) if (!cyc[v]) { dep[v]=dep[u]+p[v]; FA[v]=u; dfs(v); sz[u]+=sz[v]; if (sz[v]>sz[mxson[u]]) mxson[u]=v; } } void dfs2(int u) { dfn[u]=++idx; bk[idx]=u; D[idx]=mn[u]=dep[a[u]]+w[a[u]]; if (top[u]!=u) mn[u]=min(mn[u],mn[top[u]]); if (mxson[u]) top[mxson[u]]=top[u],dfs2(mxson[u]); for (int v : son[u]) if (!cyc[v]) { if (v==mxson[u]) continue; top[v]=v; dfs2(v); } } 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; top[i]=i; dfs2(i); 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=idx-1;i>=1;i--) { if (top[bk[i]]==top[bk[i+1]]) D[i]=min(D[i],D[i+1]); } //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; while (!cyc[y]&&now+dep[x]<mn[y]) y=FA[top[y]]; //printf("y=%d\n",y); if (!cyc[y]) { int p=upper_bound(D+dfn[top[y]],D+dfn[y]+1,now+dep[x])-D; if (p>dfn[y]) p=dfn[y]; y=bk[p]; } //printf("y=%d\n",y); if (!cyc[y]) y=FA[y]; now+=dep[x]-dep[y]; x=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[4]; 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<4;i++) { for (int j=1;j<=n;j++) { if (j==n||(s[j]>>(i*7))) 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<4;i++) { while (now<(1LL<<(i*7+7))) { 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...