Submit Info #969

Problem Lang User Status Time Memory
Dominator Tree cpp latte0119 AC 82 ms 26.38 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.68 MiB
example_01 AC 2 ms 0.68 MiB
random_00 AC 34 ms 18.30 MiB
random_01 AC 82 ms 26.38 MiB
random_02 AC 27 ms 8.92 MiB
random_03 AC 38 ms 23.80 MiB
random_04 AC 5 ms 2.67 MiB

#include<bits/stdc++.h> using namespace std; #define int long long #define rep(i,n) for(int i=0;i<(n);i++) #define pb push_back #define all(v) (v).begin(),(v).end() #define fi first #define se second typedef vector<int>vint; typedef pair<int,int>pint; typedef vector<pint>vpint; template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;} template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;} template<class A,class B> ostream& operator<<(ostream& ost,const pair<A,B>&p){ ost<<"{"<<p.first<<","<<p.second<<"}"; return ost; } template<class T> ostream& operator<<(ostream& ost,const vector<T>&v){ ost<<"{"; for(int i=0;i<v.size();i++){ if(i)ost<<","; ost<<v[i]; } ost<<"}"; return ost; } struct DominatorTree{ int n; vector<vector<int>>G,rG; vector<int>semi,id,rid,par,mn,anc; DominatorTree(int n): n(n),G(n),rG(n),semi(n), id(n,-1),rid(n),par(n,-1),mn(n),anc(n) { for(int i=0;i<n;i++){ semi[i]=mn[i]=anc[i]=i; } } void addEdge(int a,int b){ G[a].push_back(b); rG[b].push_back(a); } int find(int v){ if(anc[v]==v)return v; int a=find(anc[v]); if(id[semi[mn[anc[v]]]]<id[semi[mn[v]]])mn[v]=mn[anc[v]]; return anc[v]=a; } void link(int c,int p){ anc[c]=p; } void dfs(int v,int p,int &k){ id[v]=k; rid[k++]=v; par[v]=p; for(int c:G[v])if(id[c]==-1)dfs(c,v,k); } vector<int>calc(int root){ int sz=0; dfs(root,-1,sz); vector<int>us(n); vector<vector<int>>bucket(n); for(int i=sz-1;i>0;i--){ int w=rid[i]; for(int v:rG[w])if(id[v]!=-1){ find(v); if(id[semi[mn[v]]]<id[semi[w]])semi[w]=semi[mn[v]]; } bucket[semi[w]].pb(w); for(int v:bucket[par[w]]){ find(v); us[v]=mn[v]; } bucket[par[w]].clear(); link(w,par[w]); } vector<int>idom(n,-1); for(int i=1;i<sz;i++){ int w=rid[i]; if(semi[w]==semi[us[w]])idom[w]=semi[w]; else idom[w]=idom[us[w]]; } return idom; } }; signed main(){ int N,M,S; scanf("%lld%lld%lld",&N,&M,&S); DominatorTree dt(N); rep(i,M){ int a,b; scanf("%lld%lld",&a,&b); dt.addEdge(a,b); } auto idom=dt.calc(S); idom[S]=S; for(int i=0;i<N;i++){ if(i)printf(" "); printf("%lld",idom[i]); } puts(""); return 0; }