Submission #910795

#TimeUsernameProblemLanguageResultExecution timeMemory
910795asdasdqwerPipes (CEOI15_pipes)C++14
40 / 100
899 ms65536 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; } }; #define MAXN 100000 vector<int> st(MAXN, 0); vector<vector<int>> g; vector<vector<int>> lft; bitset<100000> vis; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n,m;cin>>n>>m; DSU d1(n), d2(n); g.assign(n, vector<int>()); 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.assign(n,0); d2.r.assign(n,0); lft.assign(n, vector<int>(18,-1)); 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; d1.r[x]=d1.r[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]; } } } for (int i=0;i<n;i++) { if (d2.p[i] == i) continue; int a=i, b=d2.get(i); d2.r[a]++; d2.r[b]++; if (d1.r[a]<d1.r[b])swap(a,b); int steps=d1.r[a]-d1.r[b]; int cnt=0; while (steps) { if ((steps&1)==1) { a=lft[a][cnt]; } steps>>=1;cnt++; } if (a==b) { d2.r[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]; } } d2.r[lft[a][0]] -= 2; } d1.r.clear(); for (int i=0;i<n;i++) { lft[i]={lft[i][0]}; } for (int i=0;i<n;i++) vis[i]=0; 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]; if (g[r].size()==0) { if (lft[r][0] != -1) { d2.r[lft[r][0]] += d2.r[r]; } pt--; continue; } for (int x:g[r]) { if (!vis[x]) { st[++pt]=x; vis[x]=true; } } g[r].clear(); } } st.clear(); for (int i=0;i<n;i++) { if (d2.r[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...