Submit Info #29612

Problem Lang User Status Time Memory
Dominator Tree cpp (anonymous) AC 72 ms 37.05 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.61 MiB
example_01 AC 1 ms 0.67 MiB
random_00 AC 29 ms 25.67 MiB
random_01 AC 72 ms 37.05 MiB
random_02 AC 17 ms 12.42 MiB
random_03 AC 38 ms 33.55 MiB
random_04 AC 3 ms 3.42 MiB

#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for(int i = a; i < (b); ++i) #define trav(i, a) for(auto& i : a) #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 Dominator { int n, co = 0; // ans (below) is down-edges of dom-tree vector<vi> adj, radj, child, sdomChild, ans; vi label, rlabel, sdom, dom, par, bes; Dominator(vector<vi> g) : n(sz(g)), adj(g), radj(n), child(n), sdomChild(n), ans(n), label(n,-1) { rlabel = sdom = dom = par = bes = label; } int get(int x) { // DSU with path compression if (par[x] != x) { int t = get(par[x]); par[x] = par[par[x]]; // ?? if (sdom[t] < sdom[bes[x]]) bes[x] = t; } // get vertex with smallest sdom on path to root return bes[x]; } void dfs(int x) { // create DFS tree label[rlabel[co] = x] = sdom[co] = par[co] = bes[co] = co; ++co; for(auto &y : adj[x]) { if (label[y] == -1) { dfs(y); child[label[x]].push_back(label[y]); } radj[label[y]].push_back(label[x]); } } void init(int root) { dfs(root); for(int i = co; i--;) { for(int j: radj[i]) sdom[i] = min(sdom[i],sdom[get(j)]); if(i) sdomChild[sdom[i]].push_back(i); for(int j : sdomChild[i]) { int k = get(j); if (sdom[j] == sdom[k]) dom[j] = sdom[j]; else dom[j] = k; } for(int j : child[i]) par[j] = i; } rep(i,1,co) { if (dom[i] != sdom[i]) dom[i] = dom[dom[i]]; ans[rlabel[dom[i]]].push_back(rlabel[i]); } // rlabel[dom[label[x]]] is parent in dom-tree } }; int main() { cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit); int n, m, s; cin >> n >> m >> s; vector<vi> g(n); rep(i,0,m) { int a,b; cin>>a>>b; g[a].emplace_back(b); } Dominator tree(g); tree.init(s); rep(i,0,n) { int k = tree.label[i]; if(k == -1) cout << -1 << " "; else if(i == s) cout << s << " "; else cout << tree.rlabel[tree.dom[k]] << " "; } cout << endl; }