Submission #1189160

#TimeUsernameProblemLanguageResultExecution timeMemory
1189160kl0989eNetwork (BOI15_net)C++20
100 / 100
226 ms75484 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define fi first #define se second #define pb push_back #define vi vector<int> #define vl vector<ll> #define pi pair<int, int> #define pl pair<ll,ll> #define all(x) (x).begin(),(x).end() const int maxn=5e5+10; vector<vi> graph(maxn); vector<pi> ans; pi dfs(int cur, int prev=-1) { vi tt; vi ttt; int a=-1; bool k=1; for (auto to:graph[cur]) { if (to==prev) { continue; } pi t=dfs(to,cur); tt.pb(t.fi); if (t.se!=-1) { ttt.pb(t.se); if (k) { a=t.fi; } } else { k=0; a=t.fi; } } if (tt.size()==1 && ttt.size()==1) { return {tt[0],ttt[0]}; } if (tt.size()==2 && !ttt.size()) { return {tt[0],tt[1]}; } if (tt.size()==0) { return {cur,-1}; } while (ttt.size()>1) { int a=ttt.back(); ttt.pop_back(); int b=ttt.back(); ttt.pop_back(); ans.pb({a,b}); } if (ttt.size()) { ans.pb({ttt.back(),a}); tt.erase(find(all(tt),a)); } while (tt.size()>2) { int a=tt.back(); tt.pop_back(); int b=tt.back(); tt.pop_back(); ans.pb({a,b}); } if (tt.size()==2) { return {tt[0],tt[1]}; } return {tt[0],-1}; } int32_t main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; int a,b; for (int i=0; i<n-1; i++) { cin >> a >> b; graph[--a].pb(--b); graph[b].pb(a); } int i=0; while (graph[i].size()==1) { i++; } pi t=dfs(i); if (t.se==-1) { ans.pb({t.fi,i}); } else { ans.pb({t.fi,t.se}); } cout << ans.size() << '\n'; for (int i=0; i<ans.size(); i++) { cout << ans[i].fi+1 << ' ' << ans[i].se+1 << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...