Submit Info #44543

Problem Lang User Status Time Memory
Dominator Tree cpp ZigZagKmp AC 115 ms 124.96 MiB

ケース詳細
Name Status Time Memory
example_00 AC 65 ms 115.46 MiB
example_01 AC 67 ms 115.51 MiB
random_00 AC 77 ms 119.16 MiB
random_01 AC 115 ms 124.96 MiB
random_02 AC 77 ms 118.00 MiB
random_03 AC 81 ms 120.55 MiB
random_04 AC 69 ms 115.68 MiB

#include<bits/stdc++.h> using namespace std; #define maxn 1000005 #define maxm 2000005 #define inf 0x3f3f3f3f #define LL long long #define ull unsigned long long #define db double #define ldb long double #define mod 1000000007 #define eps 1e-9 #define local void file(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);} template <typename Tp> void read(Tp &x){ int fh=1;char c=getchar();x=0; while(!isdigit(c)){if(c=='-'){fh=-1;}c=getchar();} while(isdigit(c)){x=(x<<1)+(x<<3)+(c&15);c=getchar();}x*=fh; } int n,m,S; vector<int>og[maxn],nog[maxn]; vector<int>G[maxn],nG[maxn]; namespace Sub1{ int dfn[maxn],ndfn[maxn],fa[maxn],tot; void dfs(int x,int pa){ fa[x]=pa;dfn[x]=++tot;ndfn[tot]=x; for(auto y:og[x]){ if(!dfn[y])dfs(y,x); } } int semi[maxn]; int ff[maxn],mn[maxn]; int fid(int x){ if(x==ff[x])return x; int pa=ff[x];ff[x]=fid(ff[x]); if(dfn[semi[mn[pa]]]<dfn[semi[mn[x]]])mn[x]=mn[pa]; return ff[x]; } void solve(){ for(int i=1;i<=n;++i)ff[i]=mn[i]=semi[i]=i; dfs(S,0); for(int i=1;i<=n;++i){ if(!dfn[i])dfn[i]=inf; } for(int i=tot,x;i>=2;--i){ x=ndfn[i]; int mi=n; for(auto y:nog[x]){ if(dfn[y]<dfn[x])mi=min(mi,dfn[y]); else fid(y),mi=min(mi,dfn[semi[mn[y]]]); } semi[x]=ndfn[mi]; ff[fid(x)]=fid(fa[x]); } for(int i=2,x;i<=tot;++i){ x=ndfn[i]; G[fa[x]].push_back(x); nG[x].push_back(fa[x]); if(semi[x]==x)continue; G[semi[x]].push_back(x); nG[x].push_back(semi[x]); } } } vector<int>tr[maxn]; namespace Sub2{ int ff[20][maxn],dep[maxn]; int rd[maxn]; void add_leaf(int x,int pa){ ff[0][x]=pa;tr[pa].push_back(x);dep[x]=dep[pa]+1; for(int j=1;j<=19;++j)ff[j][x]=ff[j-1][ff[j-1][x]]; } int lca(int x,int y){ if(dep[x]<dep[y])swap(x,y); for(int i=19;~i;--i){ if(dep[ff[i][x]]>=dep[y])x=ff[i][x]; } if(x==y)return x; for(int i=19;~i;--i){ if(ff[i][x]!=ff[i][y]){ x=ff[i][x],y=ff[i][y]; } } return ff[0][x]; } void solve(){ queue<int>q; for(int i=1;i<=n;++i){ rd[i]=nG[i].size(); } q.push(S);dep[S]=1; while(!q.empty()){ int x=q.front();q.pop(); if(nG[x].size()){ int lc=nG[x][0]; for(auto pa:nG[x])lc=lca(lc,pa); add_leaf(x,lc); } for(auto y:G[x]){ if((--rd[y])==0)q.push(y); } } } } signed main(){ read(n);read(m);read(S);++S; for(int i=1,u,v;i<=m;++i){ read(u);read(v);++u,++v; og[u].push_back(v); nog[v].push_back(u); } Sub1::solve(); Sub2::solve(); for(int i=1;i<=n;++i){ if(Sub1::dfn[i]==inf)printf("-1 "); else{ if(i==S)printf("%d ",S-1); else printf("%d ",Sub2::ff[0][i]-1); } } return 0; }