Submission #858952

#TimeUsernameProblemLanguageResultExecution timeMemory
858952Tenis0206Pipes (CEOI15_pipes)C++11
100 / 100
1644 ms15524 KiB
#include <bits/stdc++.h> using namespace std; const int nmax = 1e5; int n,m; int td[nmax + 5], rang[nmax + 5]; int lvl[nmax + 5], t[nmax + 5][17]; int sum[nmax + 5]; pair<int,int> e[nmax + 5]; vector<pair<int,int>> G[nmax + 5]; bitset<nmax + 5> ok; int nre = 0; int rep(int x) { if(x==td[x]) { return x; } return (td[x] = rep(td[x])); } int lca(int x, int y) { if(lvl[x] > lvl[y]) { swap(x,y); } int dif = lvl[y] - lvl[x]; for(int p=0; p<=16; p++) { if((dif & (1<<p))!=0) { y = t[y][p]; } } if(x==y) { return x; } for(int p=16; p>=0; p--) { if(t[x][p] && t[y][p] && t[x][p]!=t[y][p]) { x = t[x][p]; y = t[y][p]; } } return t[x][0]; } void update(int x, int y) { int l = lca(x,y); ++sum[x]; --sum[l]; ++sum[y]; --sum[l]; } void get_ans(int nod, int dad = 0) { for(auto it : G[nod]) { if(it.first==dad) { continue; } get_ans(it.first,nod); sum[nod] += sum[it.first]; if(sum[it.first] > 0) { ok[it.second] = 1; } } } void dfs_dad(int nod, int dad, int level) { lvl[nod] = level; t[nod][0] = dad; for(int p=1; p<=16; p++) { t[nod][p] = t[t[nod][p-1]][p-1]; } sum[nod] = 0; for(auto it : G[nod]) { if(it.first==dad) { continue; } dfs_dad(it.first,nod,level + 1); } } int get_root(int nod) { while(t[nod][0]) { nod = t[nod][0]; } return nod; } int main() { ios::sync_with_stdio(false); cin.tie(0); #ifdef home freopen("nr.in","r",stdin); freopen("nr.out","w",stdout); #endif // home cin>>n>>m; for(int i=1; i<=n; i++) { rang[i] = 1; td[i] = i; } for(int i=1; i<=m; i++) { int x,y; cin>>x>>y; if(rep(x) == rep(y)) { update(x,y); continue; } e[++nre] = {x,y}; int rx = rep(x); int ry = rep(y); if(rang[ry] > rang[rx]) { swap(rx,ry); swap(x,y); } td[ry] = rx; rang[rx] += rang[ry]; int r = get_root(y); get_ans(r); G[x].push_back({y,nre}); G[y].push_back({x,nre}); dfs_dad(y,x,lvl[x] + 1); } get_ans(get_root(1)); for(int i=1; i<=nre; i++) { int x = e[i].first, y = e[i].second; if(ok[i]==0) { cout<<x<<' '<<y<<'\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...