Submit Info #38864

Problem Lang User Status Time Memory
Dominator Tree cpp-acl (anonymous) AC 51 ms 25.87 MiB

ケース詳細
Name Status Time Memory
example_00 AC 12 ms 19.05 MiB
example_01 AC 12 ms 18.74 MiB
random_00 AC 25 ms 22.86 MiB
random_01 AC 51 ms 25.87 MiB
random_02 AC 20 ms 21.05 MiB
random_03 AC 28 ms 24.02 MiB
random_04 AC 12 ms 19.48 MiB

#include<bits/stdc++.h> using namespace std ; #define ll long long #define pb push_back #define all(v) v.begin(),v.end() #define sz(a) (ll)a.size() #define F first #define S second #define INF 2000000000000000000 #define popcount(x) __builtin_popcountll(x) #define pll pair<ll,ll> #define pii pair<int,int> #define ld long double const int M = 1000000007; const int MM = 998244353; const long double PI = acos(-1); template<typename T, typename U> static inline void amin(T &x, U y){ if(y<x) x=y; } template<typename T, typename U> static inline void amax(T &x, U y){ if(x<y) x=y; } template<typename T, typename U> ostream& operator<<(ostream &os, const pair<T, U> &p) { return os<<'('<<p.F<< ","<<p.S<<')'; } const int N = 200005; vector<int> v[N]; namespace D { vector<int> rg[N],bucket[N]; vector<int> g[N]; int sdom[N],idom[N],idx[N]; int pos[N],par[N]; // Dsu // using namespace D; int p[N],min_sdom[N]; int cur = 1; void clear(int n) { cur = 1; for(int i=0;i<=n;++i) { g[i].clear(),v[i].clear(),rg[i].clear(),bucket[i].clear(); pos[i] = 0,idx[i] = 0; par[i] = 0; p[i] = i,min_sdom[i] = i; sdom[i] = i; } } void dfs(int s) { idx[s] = cur++; pos[idx[s]] = s; for(auto j:g[s]) { if(!idx[j]) { par[j] = s; dfs(j); } rg[idx[j]].pb(idx[s]); } } // Path Compression only, Amortized it is also nlogn pii get(int u) { if(p[u]==u) return make_pair(min_sdom[u],u); auto k = get(p[u]); p[u] = k.second; if(sdom[k.first]<sdom[min_sdom[u]]) min_sdom[u] = k.first; return make_pair(min_sdom[u],k.second); } void dom_tree(int root) { dfs(root); for(int i=cur-1;i>=1;--i) { for(auto &j:rg[i]) { sdom[i] = min(sdom[i],sdom[get(j).first]); } if(i>=1) bucket[sdom[i]].pb(i); for(auto &j:bucket[i]) { int u = get(j).first; if(sdom[u]==i) idom[j] = i; else idom[j] = u; } for(auto &j:g[pos[i]]) if(par[j] == pos[i]) p[idx[j]] = i; } for(int i=2;i<cur;++i) { if(idom[i]!=sdom[i]) idom[i] = idom[idom[i]]; v[pos[idom[i]]].pb(pos[i]); v[pos[i]].pb(pos[idom[i]]); } } } // using namespace D; // D::clear(n); // D::dom_tree(root); int ans[N]; void dfs(int s,int p) { ans[s] = p; for(auto j:v[s]) { if(j!=p) dfs(j,s); } } int _runtimeTerror_() { int n,m,s; cin>>n>>m>>s; ++s; D::clear(n); for(int i=0;i<m;++i) { int x,y; cin>>x>>y; ++x,++y; D::g[x].push_back(y); } D::dom_tree(s); dfs(s,s); for(int i=1;i<=n;++i) cout<<ans[i]-1<<" "; cout<<"\n"; return 0; } int main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #ifdef runSieve sieve(); #endif #ifdef NCR initialize(); #endif int TESTS=1; //cin>>TESTS; while(TESTS--) _runtimeTerror_(); return 0; }