Submit Info #60485

Problem Lang User Status Time Memory
Dominator Tree cpp Golovanov399 AC 65 ms 28.15 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.41 MiB
example_01 AC 1 ms 0.42 MiB
random_00 AC 25 ms 20.09 MiB
random_01 AC 65 ms 28.15 MiB
random_02 AC 16 ms 9.46 MiB
random_03 AC 36 ms 26.23 MiB
random_04 AC 3 ms 2.57 MiB

#include <bits/stdc++.h> #define all(x) (x).begin(), (x).end() #define make_unique(x) sort((x).begin(), (x).end()); (x).erase(unique((x).begin(), (x).end()), (x).end()) #define imie(x) #x << ": " << x using namespace std; using li = long long; using LI = __int128_t; using ld = long double; using uint = unsigned int; using ull = unsigned long long; ostream& operator <<(ostream& ostr, LI x) { static constexpr li BIG = 1e18; if (x < 0) { ostr << "-"; x = -x; } if (x < BIG) { return ostr << (li)x; } else if (x / BIG >= BIG) { stringstream ss; ss << setfill('0') << setw(18) << (li)(x / BIG % BIG); ss << setfill('0') << setw(18) << (li)(x % BIG); return ostr << (li)(x / BIG / BIG) << ss.str(); } else { stringstream ss; ss << setfill('0') << setw(18) << (li)(x % BIG); return ostr << (li)(x / BIG) << ss.str(); } } template <typename T> ostream& operator <<(ostream& ostr, const vector<T>& vec) { auto [pre, sep, post] = (&ostr == &cout) ? make_tuple("", " ", "") : make_tuple("[", ", ", "]"); ostr << pre; bool fp = true; for (const auto& x : vec) { if (fp) { fp = false; } else { ostr << sep; } ostr << x; } return ostr << post; } template <typename T, size_t N> ostream& operator <<(ostream& ostr, const array<T, N>& vec) { auto [pre, sep, post] = (&ostr == &cout) ? make_tuple("", " ", "") : make_tuple("[", ", ", "]"); ostr << pre; bool fp = true; for (const auto& x : vec) { if (fp) { fp = false; } else { ostr << sep; } ostr << x; } return ostr << post; } template <typename T> ostream& operator <<(ostream& ostr, const set<T>& st) { auto [pre, sep, post] = (&ostr == &cout) ? make_tuple("", " ", "") : make_tuple("{", ", ", "}"); ostr << pre; bool fp = true; for (const auto& x : st) { if (fp) { fp = false; } else { ostr << sep; } ostr << x; } return ostr << post; } template <typename T> ostream& operator <<(ostream& ostr, const multiset<T>& st) { auto [pre, sep, post] = (&ostr == &cout) ? make_tuple("", " ", "") : make_tuple("{", ", ", "}"); ostr << pre; bool fp = true; for (const auto& x : st) { if (fp) { fp = false; } else { ostr << sep; } ostr << x; } return ostr << post; } template <typename T, typename U> ostream& operator <<(ostream& ostr, const map<T, U>& mp) { ostr << "{"; bool fp = true; for (const auto& [k, v] : mp) { if (fp) { fp = false; } else { ostr << ", "; } ostr << k << ": " << v; } return ostr << "}"; } template <typename T, typename U> ostream& operator <<(ostream& ostr, const pair<T, U>& p) { return ostr << "(" << p.first << ", " << p.second << ")"; } #define all(x) (x).begin(), (x).end() #define itn int #define make_unique(x) sort((x).begin(), (x).end()); (x).erase(unique((x).begin(), (x).end()), (x).end()) inline int nxt() { int x; scanf("%d", &x); return x; } struct DominatorTree { int n; int root; vector<int> tin, revin; vector<int> sdom, idom; vector<vector<int>> g, revg; vector<int> parent; vector<int> dsu; vector<int> min_v; int cnt = 0; int get(int v) { ++cnt; if (dsu[v] == v) { return v; } int next_v = get(dsu[v]); if (sdom[min_v[dsu[v]]] < sdom[min_v[v]]) { min_v[v] = min_v[dsu[v]]; } dsu[v] = next_v; return next_v; } void merge(int from, int to) { dsu[from] = to; } DominatorTree(int n, int root): n(n), root(root), dsu(n) { tin.resize(n, -1); revin.resize(n, -1); sdom.resize(n); idom.resize(n); g.resize(n); revg.resize(n); dsu.resize(n); parent.assign(n, -1); min_v.assign(n, -1); for (int i = 0; i < n; ++i) { dsu[i] = i; min_v[i] = i; sdom[i] = i; idom[i] = i; } } void dfs(int v, vector<vector<int>>& cur_g, int& timer) { tin[v] = timer++; for (int to : cur_g[v]) { if (tin[to] == -1) { dfs(to, cur_g, timer); parent[tin[to]] = tin[v]; } revg[tin[to]].push_back(tin[v]); } } vector<int> get_tree(vector<vector<int>> cur_g) { vector<char> used(n, false); int timer = 0; dfs(root, cur_g, timer); for (int i = 0; i < n; ++i) { if (tin[i] == -1) { continue; } revin[tin[i]] = i; for (int to : cur_g[i]) { g[tin[i]].push_back(tin[to]); } } vector<vector<int>> buckets(n); for (int i = n - 1; i >= 0; --i) { for (int to : revg[i]) { get(to); sdom[i] = min(sdom[i], sdom[min_v[to]]); } if (revin[i] == -1) { continue; } if (i) { buckets[sdom[i]].push_back(i); } for (int w : buckets[i]) { get(w); int v = min_v[w]; if (sdom[v] == sdom[w]) { idom[w] = sdom[w]; } else { idom[w] = v; } } for (int to : g[i]) { if (parent[to] == i) { merge(to, i); } } } for (int i = 0; i < n; ++i) { if (revin[i] == -1) { continue; } if (idom[i] == sdom[i]) { continue; } else { idom[i] = idom[idom[i]]; } } vector<int> res(n, -1); for (int i = 0; i < n; ++i) { if (revin[i] == -1) { continue; } res[revin[i]] = revin[idom[i]]; } return res; } }; int main() { int n = nxt(), m = nxt(); int root = nxt(); vector<vector<int>> g(n); for (int i = 0; i < m; ++i) { int u = nxt(), v = nxt(); g[u].push_back(v); } auto tree = DominatorTree(n, root).get_tree(g); cout << tree << "\n"; return 0; }