Submit Info #11754

Problem Lang User Status Time Memory
Dominator Tree cpp firiexp AC 88 ms 21.26 MiB

ケース詳細
Name Status Time Memory
example_00 AC 3 ms 0.68 MiB
example_01 AC 2 ms 0.68 MiB
random_00 AC 31 ms 14.30 MiB
random_01 AC 88 ms 21.26 MiB
random_02 AC 22 ms 7.17 MiB
random_03 AC 39 ms 18.55 MiB
random_04 AC 6 ms 2.18 MiB

#include <iostream> #include <algorithm> #include <map> #include <set> #include <queue> #include <stack> #include <numeric> #include <bitset> #include <cmath> static const int MOD = 1000000007; using ll = long long; using u32 = unsigned; using u64 = unsigned long long; using namespace std; class DominatorTree { int n; void unite(int x, int y){ uf_par[y] = x; } int compress(int x){ if(uf_par[x] == x) return x; int r = compress(uf_par[x]); if(semi[m[x]] > semi[m[uf_par[x]]]) m[x] = m[uf_par[x]]; return uf_par[x] = r; } int eval(int x){ compress(x); return m[x]; } void dfs(int x, int &cur){ semi[x] = cur; ord[cur++] = x; for (auto &&i : G[x]) { if(!~semi[i]){ par[i] = x; dfs(i, cur); } } } public: DominatorTree(int n) : n(n), G(n), Grev(n), idom(n), semi(n), ord(n), par(n), uf_par(n), m(n), tmp(n), U(n) {} vector<vector<int>> G, Grev, tmp; vector<int> semi, ord, par, uf_par, m, U, idom; void add_edge(int a, int b){ G[a].emplace_back(b); Grev[b].emplace_back(a); } void build(int root){ for (int i = 0; i < n; ++i) uf_par[i] = i, m[i] = i, semi[i] = -1, idom[i] = -1; int cur = 0; dfs(root, cur); for (int i = cur-1; i >= 0; --i) { int a = ord[i]; for (auto &&b : Grev[a]) { if(~semi[b]){ int c = eval(b); semi[a] = min(semi[a], semi[c]); } } tmp[ord[semi[a]]].emplace_back(a); for (auto &&b : tmp[par[a]]) U[b] = eval(b); tmp[par[a]].clear(); unite(par[a], a); } for (int i = 1; i < cur; ++i) { int a = ord[i], b = U[a]; if(semi[a] == semi[b]) idom[a] = semi[a]; else idom[a] = idom[b]; } for (int i = 1; i < cur; ++i) { int a = ord[i]; idom[a] = ord[idom[a]]; } idom[root] = -1; } }; template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208; 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(i) printf(" "); printf("%d", (i == s ? s : G.idom[i])); } puts(""); return 0; }