Submission #1213438

#TimeUsernameProblemLanguageResultExecution timeMemory
1213438minhpkNetwork (BOI15_net)C++20
0 / 100
21 ms47168 KiB
#include <bits/stdc++.h> #define int long long using namespace std; int a; vector <int> z[1000005]; int root; int par[1000005]; vector <int> sz[1000005]; int k; int find(int u){ if (par[u]==u){ return u; } return par[u]=find(par[u]); } void join(int x,int y){ x=find(x); y=find(y); if (x==y){ return; } while ( (sz[x].size()>1 || sz[y].size()>1) && sz[x].size() && sz[y].size()){ cout << sz[x].back() << " " << sz[y].back() << "\n"; sz[x].pop_back(); sz[y].pop_back(); } par[y]=x; while (sz[y].size()){ int p=sz[y].back(); sz[x].push_back(p); sz[y].pop_back(); } } void dfs(int i,int parent){ for (auto p:z[i]){ if (p==parent){ continue; } dfs(p,i); join(i,p); } } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> a; for (int i=1;i<a;i++){ int x,y; cin >> x >> y; z[x].push_back(y); z[y].push_back(x); } for (int i=1;i<=a;i++){ if (z[i].size()!=1){ root=i; } } for (int i=1;i<=a;i++){ par[i]=i; } for (int i=1;i<=a;i++){ if (z[i].size()==1){ sz[i].push_back(i); k++; } } cout << (k+1)/2 << "\n"; dfs(root,0); int x=find(root); if (x%2==0){ for (int i=0;i<sz[x].size();i+=2){ cout << sz[x][i] << " " << sz[x][i+1] << "\n"; } }else{ sz[x].push_back(root); for (int i=0;i<sz[x].size();i+=2){ cout << sz[x][i] << " " << sz[x][i+1] << "\n"; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...