Submit Info #37393

Problem Lang User Status Time Memory
Dominator Tree cpp neko AC 58 ms 25.30 MiB

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.67 MiB
example_01 AC 1 ms 0.67 MiB
random_00 AC 23 ms 17.72 MiB
random_01 AC 58 ms 25.30 MiB
random_02 AC 16 ms 8.67 MiB
random_03 AC 31 ms 23.05 MiB
random_04 AC 4 ms 2.55 MiB

#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for(int i = a; i < (b); ++i) #define all(x) begin(x), end(x) #define sz(x) (int)(x).size() typedef long long ll; typedef pair<int, int> pii; typedef vector<int> vi; struct DTree{ int cs = 0, n; vector<vi> e, re, rdom; vi s, rs, par, val, sdom, rp, dom; DTree(vector<vi> &g) : n(sz(g)), e(g), re(n), rdom(n), s(n, -1), rs(n), par(n), val(n), sdom(n), rp(n), dom(n) {} int find(int x, int c = 0) { if (par[x] == x) return c ? -1 : x; int p = find(par[x], 1); if (p == -1) return c ? par[x] : val[x]; if (sdom[val[x]] > sdom[val[par[x]]]) val[x] = val[par[x]]; par[x] = p; return c ? p : val[x]; } void merge(int x, int y) { par[x] = y; } void dfs(int x) { rs[s[x] = cs++] = x; par[cs] = sdom[cs] = val[cs] = cs; for (int e: e[x]) { if (s[e] == -1) dfs(e), rp[s[e]] = s[x]; re[s[e]].push_back(s[x]); } } vi build(int src) { dfs(src); for (int i = cs-1; i >= 0; i--) { for (int e: re[i]) sdom[i] = min(sdom[i], sdom[find(e)]); if (i != src) rdom[sdom[i]].push_back(i); for (int e: rdom[i]) { int p = find(e); if (sdom[p] == i) dom[e] = i; else dom[e] = p; } if (i != src) merge(i, rp[i]); } rep(i, 0, cs) if (sdom[i] != dom[i]) dom[i] = dom[dom[i]]; vi up(sz(e), -1); rep(i, 0, cs) up[rs[i]] = rs[dom[i]]; return up; } }; signed main() { ios::sync_with_stdio(0); cin.tie(0); int n, m, s; cin >> n >> m >> s; vector<vi> g(n); while (m--) { int u, v; cin >> u >> v; g[u].push_back(v); } DTree dm(g); vi par = dm.build(s); for (int i: par) cout << i << ' '; return 0; }