Submit Info #7089

Problem Lang User Status Time Memory
Dominator Tree cpp chocorusk AC 87 ms 25.30 MiB

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.72 MiB
example_01 AC 1 ms 0.67 MiB
random_00 AC 30 ms 17.72 MiB
random_01 AC 87 ms 25.30 MiB
random_02 AC 18 ms 8.65 MiB
random_03 AC 33 ms 23.05 MiB
random_04 AC 4 ms 2.55 MiB

#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <cmath> #include <bitset> #include <vector> #include <map> #include <set> #include <queue> #include <deque> #include <algorithm> #include <complex> #include <unordered_map> #include <unordered_set> #include <random> #include <cassert> #include <fstream> #include <utility> #include <functional> #include <time.h> #include <stack> #include <array> #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair<int, int> P; template<typename T> struct unionfind_pathmin{ vector<int> par; vector<T> mn; const T e; unionfind_pathmin() {} unionfind_pathmin(int n, const T &e):e(e), par(n), mn(n, e){ for(int i=0; i<n; i++) par[i]=i; } int find(int x){ if(par[x]==x) return x; int r=find(par[x]); mn[x]=min(mn[x], mn[par[x]]); return par[x]=r; } T eval(int x){//min path[root, x] find(x); return mn[x]; } void unite(int x, int y){ par[y]=x; } }; struct DominatorTree{ int n; vector<vector<int>> g, gr, tree, v; vector<int> idx, rev, idom, sdom, u; unionfind_pathmin<pair<int, int>> uf; DominatorTree(int n):n(n), g(n), gr(n), tree(n), v(n), u(n), rev(n), idom(n), sdom(n, n), idx(n, -1), uf(n, make_pair(1<<30, 1<<30)){} void add_edge(int a, int b){ g[a].push_back(b); gr[b].push_back(a); } void dfs(int x, int &t){ idx[x]=t++; rev[idx[x]]=x; for(auto y:g[x]){ if(idx[y]==-1){ dfs(y, t); tree[x].push_back(y); } } } void build(int root){ int t=0; dfs(root, t); for(int i=t-1; i>=0; i--){ int x=rev[i]; for(auto y:v[x]){ auto p=uf.eval(y); u[y]=p.second; } if(i==0) break; for(auto y:gr[x]){ if(idx[y]==-1) continue; auto p=uf.eval(y); if(p.first<n && (sdom[x]==n || idx[p.first]<idx[sdom[x]])) sdom[x]=p.first; if(idx[y]<i){ if(sdom[x]==n || idx[y]<idx[sdom[x]]) sdom[x]=y; } } uf.mn[x]=make_pair(sdom[x], x); for(auto y:tree[x]){ uf.unite(x, y); } v[sdom[x]].push_back(x); } for(int i=1; i<t; i++){ int x=rev[i]; if(sdom[x]==sdom[u[x]]) idom[x]=sdom[x]; else idom[x]=idom[u[x]]; } idom[root]=root; } }; int main() { int n, m, s; scanf("%d %d %d", &n, &m, &s); DominatorTree g(n); for(int i=0; i<m; i++){ int a, b; scanf("%d %d", &a, &b); g.add_edge(a, b); } g.build(s); for(int i=0; i<n; i++){ if(g.idx[i]==-1) printf("-1 "); else printf("%d ", g.idom[i]); } printf("\n"); return 0; }