Submit Info #7057

Problem Lang User Status Time Memory
Dominator Tree cpp TKO919 AC 111 ms 21.56 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.45 MiB
example_01 AC 1 ms 0.42 MiB
gen_tree_00 AC 96 ms 17.96 MiB
gen_tree_01 AC 92 ms 18.22 MiB
gen_tree_02 AC 106 ms 17.97 MiB
gen_tree_2_00 AC 110 ms 20.03 MiB
gen_tree_2_01 AC 111 ms 20.02 MiB
gen_tree_2_02 AC 109 ms 20.04 MiB
random_00 AC 21 ms 14.37 MiB
random_01 AC 75 ms 21.56 MiB
random_02 AC 14 ms 7.20 MiB
random_03 AC 28 ms 18.94 MiB
random_04 AC 3 ms 1.95 MiB

#define _USE_MATH_DEFINES #include <bits/stdc++.h> using namespace std; //template #define rep(i,a,b) for(int i=(a);i<(b);i++) #define rrep(i,a,b) for(int i=(a);i>(b);i--) #define ALL(v) (v).begin(),(v).end() typedef long long int ll; const int inf = 0x3fffffff; const ll INF = 0x1fffffffffffffff; const double eps=1e-12; void tostr(ll x,string& res){while(x)res+=('0'+(x%10)),x/=10; reverse(ALL(res)); return;} template<class T> inline bool chmax(T& a,T b){ if(a<b){a=b;return 1;}return 0; } template<class T> inline bool chmin(T& a,T b){ if(a>b){a=b;return 1;}return 0; } //end class Dominator{ int idx=0,n; vector<int> p,m; vector<int> par,ord,sdom,U,idom; vector<vector<int>> bucket,g,rev; int root(int v){ if(p[v]==v)return v; int rt=root(p[v]); if(sdom[m[v]]>sdom[m[p[v]]])m[v]=m[p[v]]; return p[v]=rt; } int eval(int v){root(v); return m[v];} void unite(int x,int y){p[y]=x;} //union-find end void dfs(int v){ sdom[v]=idx; ord[idx++]=v; for(int nxt:g[v])if(sdom[nxt]<0){par[nxt]=v; dfs(nxt);} } public: Dominator(int _n):idx(0),n(_n),p(_n),m(_n), par(_n),ord(_n,-1),sdom(_n,-1),U(_n),idom(_n,-1),bucket(_n),g(_n),rev(_n){ rep(i,0,n)p[i]=m[i]=i; } void add_edge(int u,int v){g[u].push_back(v); rev[v].push_back(u);} vector<int> run(int rt){ dfs(rt); rrep(i,n-1,0){ int w=ord[i]; if(w==-1)continue; for(int nxt:rev[w])if(sdom[nxt]>=0){ int u=eval(nxt); chmin(sdom[w],sdom[u]); } bucket[ord[sdom[w]]].push_back(w); for(int v:bucket[par[w]])U[v]=eval(v); bucket[par[w]].clear(); unite(par[w],w); } rep(i,1,n){ int w=ord[i]; if(w<0)continue; int u=U[w]; if(sdom[w]==sdom[u])idom[w]=sdom[w]; else idom[w]=idom[u]; } rep(i,1,n){int w=ord[i]; if(w>=0)idom[w]=ord[idom[w]];} idom[rt]=rt; return idom; } }; int main(){ int n,m,rt; scanf("%d%d%d",&n,&m,&rt); Dominator g(n); rep(_,0,m){ int u,v; scanf("%d%d",&u,&v); g.add_edge(u,v); } auto res=g.run(rt); rep(i,0,n)printf("%d ",res[i]); return 0; }