Submit Info #41964

Problem Lang User Status Time Memory
Dominator Tree cpp wleungBVG AC 51 ms 17.22 MiB

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.67 MiB
example_01 AC 1 ms 0.68 MiB
random_00 AC 15 ms 11.61 MiB
random_01 AC 51 ms 17.22 MiB
random_02 AC 10 ms 5.87 MiB
random_03 AC 26 ms 15.05 MiB
random_04 AC 2 ms 1.92 MiB

// https://judge.yosupo.jp/problem/dominatortree #include <bits/stdc++.h> using namespace std; template <class C> constexpr int sz(const C &c) { return int(c.size()); } constexpr const char nl = '\n', sp = ' '; using uint = unsigned int; using ll = long long; using ull = unsigned long long; using ld = long double; #if __SIZEOF_INT128__ using i128 = __int128_t; using ui128 = __uint128_t; #endif struct DominatorTree { int V, ind; vector<int> idom, sdom, par, ord, U, UF, m; vector<vector<int>> bucket, H; int find(int v) { if (UF[v] == v) return v; int fv = find(UF[v]); if (sdom[m[v]] > sdom[m[UF[v]]]) m[v] = m[UF[v]]; return UF[v] = fv; } int eval(int v) { find(v); return m[v]; } template <class Digraph> void dfs(const Digraph &G, int v) { ord[sdom[v] = ind++] = v; for (int w : G[v]) if (sdom[w] == -1) { par[w] = v; dfs(G, w); } } template <class Digraph> DominatorTree(const Digraph &G, int root) : V(G.size()), ind(0), idom(V, -1), sdom(V, -1), par(V, -1), ord(V, -1), U(V, -1), UF(V), m(V), bucket(V), H(V) { for (int v = 0; v < V; v++) { UF[v] = m[v] = v; for (int w : G[v]) H[w].push_back(v); } dfs(G, root); for (int i = ind - 1; i > 0; i--) { int w = ord[i]; for (int v : H[w]) if (sdom[v] >= 0) sdom[w] = min(sdom[w], sdom[eval(v)]); bucket[ord[sdom[w]]].push_back(w); for (int v : bucket[par[w]]) U[v] = eval(v); bucket[UF[w] = par[w]].clear(); } for (int i = 1; i < ind; i++) { int w = ord[i], u = U[w]; idom[w] = sdom[sdom[w] == sdom[u] ? w : u]; } for (int i = 1; i < ind; i++) { int w = ord[i]; idom[w] = ord[idom[w]]; } } }; struct StaticGraph { vector<int> ST, TO, A, B; StaticGraph(int V) : ST(V + 1, 0) {} void reserveDiEdges(int maxEdges) { TO.reserve(maxEdges); A.reserve(maxEdges); B.reserve(maxEdges); } void addDiEdge(int from, int to) { ST[from]++; A.push_back(from); B.push_back(to); } void addBiEdge(int v, int w) { addDiEdge(v, w); addDiEdge(w, v); } void build() { partial_sum(ST.begin(), ST.end(), ST.begin()); TO = B; for (int e = 0; e < int(A.size()); e++) TO[--ST[A[e]]] = B[e]; } struct Iterator { const StaticGraph &G; int i; Iterator(const StaticGraph &G, int i) : G(G), i(i) {} Iterator &operator ++ () { i++; return *this; } int operator * () const { return G.TO[i]; } bool operator != (const Iterator &it) const { return i != it.i; } }; struct Adj { const StaticGraph &G; int v; Adj(const StaticGraph &G, int v) : G(G), v(v) {} const Iterator begin() const { return Iterator(G, G.ST[v]); } const Iterator end() const { return Iterator(G, G.ST[v + 1]); } }; const Adj operator [] (int v) const { return Adj(*this, v); } int size() const { return int(ST.size()) - 1; } }; int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); // freopen("err.txt", "w", stderr); ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int N, M, S; cin >> N >> M >> S; StaticGraph G(N); for (int i = 0; i < M; i++) { int a, b; cin >> a >> b; G.addDiEdge(a, b); } G.build(); DominatorTree dt(G, S); for (int i = 0; i < N; i++) cout << (i == S ? S : dt.idom[i]) << " \n"[i == N - 1]; return 0; }