Submission #910091

#TimeUsernameProblemLanguageResultExecution timeMemory
910091asdasdqwerPipes (CEOI15_pipes)C++14
70 / 100
778 ms18652 KiB
#include <bits/stdc++.h> using namespace std; struct DSU { vector<int> p,r; DSU(int n) : p(n),r(n,1) { for (int i=0;i<n;i++)p[i]=i; } int get(int i) { if (p[i]!=i && p[i]!=p[p[i]]) p[i]=get(p[i]); return p[i]; } bool unite(int a,int b) { a=get(a),b=get(b); if (a==b)return false; if (r[a]<r[b])swap(a,b); p[b]=a; r[a]+=r[b]; return true; } }; vector<int> st(1e5+1, 0); int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n,m;cin>>n>>m; DSU d1(n), d2(n); vector<vector<int>> g(n); for (int i=0;i<m;i++) { int a,b;cin>>a>>b;a--;b--; if (d1.unite(a,b)) { g[a].push_back(b); g[b].push_back(a); } else { d2.unite(a,b); } } d1.r.clear(); d2.r.clear(); vector<vector<int>> lft(n, vector<int>(18, -1)); bitset<100001> vis; vector<int> d(n,0); for (int i=0;i<n;i++) { if (vis[i]) continue; int pt=0; st[pt]=i; vis[i]=true; while (pt != -1) { int r=st[pt--]; for (int x:g[r]) { if (!vis[x]) { vis[x]=true; lft[x][0]=r; d[x]=d[r]+1; st[++pt]=x; } } } } for (int j=1;j<18;j++) { for (int i=0;i<n;i++) { lft[i][j]=lft[i][j-1]; if (lft[i][j] != -1) { lft[i][j]=lft[lft[i][j]][j-1]; } } } vector<int> dp(n, 0); for (int i=0;i<n;i++) { if (d2.p[i] == i) continue; int a=i, b=d2.get(i); dp[a]++; dp[b]++; if (d[a]<d[b])swap(a,b); int steps=d[a]-d[b]; int cnt=0; while (steps) { if ((steps&1)==1) { a=lft[a][cnt]; } steps>>=1;cnt++; } if (a==b) { dp[a]-=2; continue; } for (int i=17;i>-1;--i) { if (lft[a][i] != lft[b][i]) { a=lft[a][i]; b=lft[b][i]; } } dp[lft[a][0]] -= 2; } for (int i=0;i<n;i++) vis[i]=0; function<void(int)> dfs2=[&](int node) { vis[node]=true; for (int x:g[node]) { if (vis[x])continue; dfs2(x); dp[node]+=dp[x]; } }; for (int i=0;i<n;i++) { st[i]=-1; } for (int i=0;i<n;i++) { if (vis[i])continue; int pt=0; vis[i]=true; st[0]=i; while (pt != -1) { int r=st[pt]; for (int x:g[r]) { if (!vis[x]) { st[++pt]=x; vis[x]=true; } } if (r == st[pt]) { if (lft[r][0] != -1) { dp[lft[r][0]] += dp[r]; } st[pt]=-1; pt--; } } } for (int i=0;i<n;i++) { if (dp[i]==0 && lft[i][0] != -1) { cout<<i+1<<" "<<lft[i][0]+1<<"\n"; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...