Submit Info #40852

Problem Lang User Status Time Memory
Dominator Tree cpp-acl s123456 AC 78 ms 34.74 MiB

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.67 MiB
example_01 AC 2 ms 0.36 MiB
random_00 AC 33 ms 23.57 MiB
random_01 AC 78 ms 34.74 MiB
random_02 AC 21 ms 11.55 MiB
random_03 AC 42 ms 30.99 MiB
random_04 AC 0 ms 3.24 MiB

#include <stdio.h> #include <bits/stdc++.h> using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i) #define modulo 1000000007 #define mod(mod_x) ((((long long)mod_x+modulo))%modulo) #define Inf 10000000 void check(){ static int i = 0; //cout<<i<<endl; i++; } struct dominator_tree{ struct potentialized_dsu { using S = pair<int,int>; public: potentialized_dsu() : _n(0) {} potentialized_dsu(int n) : _n(n), parent_or_size(n, -1), d(n,e()) {} int merge(int a, int b, S v) { assert(0 <= a && a < _n); assert(0 <= b && b < _n); int x = leader(a), y = leader(b); if (x == y) return x; d[y] = op(d[y],op(d[x],v)); parent_or_size[x] += parent_or_size[y]; parent_or_size[y] = x; return x; } bool same(int a, int b) { assert(0 <= a && a < _n); assert(0 <= b && b < _n); return leader(a) == leader(b); } int leader(int a) { assert(0 <= a && a < _n); if (parent_or_size[a] < 0) return a; int l = leader(parent_or_size[a]); if(parent_or_size[a] != l){ d[a] = op(d[parent_or_size[a]],d[a]); parent_or_size[a] = l; } return parent_or_size[a]; } int size(int a) { assert(0 <= a && a < _n); return -parent_or_size[leader(a)]; } S get(int a){ assert(0 <= a && a < _n); leader(a); return d[a]; } std::vector<std::vector<int>> groups() { std::vector<int> leader_buf(_n), group_size(_n); for (int i = 0; i < _n; i++) { leader_buf[i] = leader(i); group_size[leader_buf[i]]++; } std::vector<std::vector<int>> result(_n); for (int i = 0; i < _n; i++) { result[i].reserve(group_size[i]); } for (int i = 0; i < _n; i++) { result[leader_buf[i]].push_back(i); } result.erase( std::remove_if(result.begin(), result.end(), [&](const std::vector<int>& v) { return v.empty(); }), result.end()); return result; } pair<int,int> op(pair<int,int> a,pair<int,int> b){ return min(a,b); } pair<int,int> e(){ return make_pair(1000000000,0); } private: int _n; // root node: -1 * component size // otherwise: parent std::vector<int> parent_or_size; std::vector<S> d; }; dominator_tree(){ } vector<vector<int>> get(vector<vector<int>> E,int r){ check(); int n = E.size(); vector<int> ind; vector<int> pos(n,n); vector<vector<int>> EE(n); dfs(r,E,ind,pos,EE); check(); vector<vector<int>> rE(n); rep(i,E.size()){ rep(j,E[i].size()){ rE[E[i][j]].push_back(i); } } check(); vector<pair<int,int>> sdom(n,make_pair(n,n)); vector<pair<int,int>> idom(n,make_pair(n,n)); vector<vector<int>> L(n); potentialized_dsu D(n); for(int i=ind.size()-1;i>=1;i--){ int u = ind[i]; rep(j,rE[u].size()){ int v = rE[u][j]; if(pos[u]>pos[v])sdom[u] = min(sdom[u],make_pair(pos[v],v)); sdom[u] = min(sdom[u],D.get(v)); if(pos[u]<pos[v]){ sdom[u] = min(sdom[u],sdom[v]); } } idom[u] = make_pair(sdom[u].first,u); rep(j,L[u].size()){ int v = L[u][j]; idom[v] = min(idom[v],D.get(v)); } rep(j,EE[u].size()){ int v = EE[u][j]; D.merge(u,v,make_pair(sdom[u].first,u)); } L[sdom[u].second].push_back(u); } check(); rep(i,ind.size()){ if(i==0)continue; int u = ind[i]; if(idom[u].first==n){ idom[u] = make_pair(sdom[u].first,u); } else if(sdom[u].first == sdom[idom[u].second].first){ idom[u] = sdom[u]; } else{ idom[u] = idom[idom[u].second]; } } check(); vector<vector<int>> ret(n); rep(i,n){ if(idom[i].first==n)continue; ret[idom[i].second].push_back(i); } return ret; } void dfs(int cur,vector<vector<int>> &E,vector<int> &ind,vector<int> &pos,vector<vector<int>> &EE){ pos[cur] = ind.size(); ind.push_back(cur); rep(i,E[cur].size()){ int to = E[cur][i]; if(pos[to]!=E.size())continue; EE[cur].push_back(to); dfs(to,E,ind,pos,EE); } } }; int main(){ int n,m,s; scanf("%d %d %d",&n,&m,&s); vector<vector<int>> E(n); rep(i,m){ int a,b; scanf("%d %d",&a,&b); E[a].push_back(b); } dominator_tree D; auto ret = D.get(E,s); vector<int> p(n,-1); p[s] = s; rep(i,ret.size()){ rep(j,ret[i].size()){ int to = ret[i][j]; p[to] = i; } } rep(i,n){ if(i!=0)printf(" "); printf("%d",p[i]); } cout<<endl; return 0; }