Submission #1189049

#TimeUsernameProblemLanguageResultExecution timeMemory
1189049pxsitNetwork (BOI15_net)C++20
18 / 100
284 ms14244 KiB
#include <bits/stdc++.h> using namespace std; int n,m,k,q; vector<int> adj[(int)5e5+5]; vector<int> dep((int)5e5+5); vector<pair<int,int>> vs; void dfs(int x, int i){ if(adj[x].size() == 1){ vs.emplace_back(dep[x], x); return; } for(auto to:adj[x]){ if(to == i) continue; dep[to] = dep[x] + 1; dfs(to, x); } } int main(){ cin >> n; for(int i = 2; i <= n; i++){ int a,b; cin >> a >> b; adj[a].push_back(b); adj[b].push_back(a); } vector<pair<int,int>> u; int sz = INT_MAX; for(int i = 1; i <= n; i++){ vector<pair<int,int>> ans; vector<int> op; for(auto to : adj[i]){ dep[to] = 1; vs.clear(); dfs(to, i); sort(vs.begin(), vs.end(), greater<pair<int,int>>()); ans.emplace_back(i, vs[0].second); for(int j = 2; j < vs.size(); j += 2){ ans.emplace_back(vs[j-1].second, vs[j].second); } if(vs.size() % 2 == 0){ op.push_back(vs.back().second); } } for(int k = 1; k < op.size(); k += 2){ ans.emplace_back(op[k-1], op[k]); } if(op.size() % 2 == 1){ ans.emplace_back(op.back(), i); } if(sz > ans.size()){ u = ans; sz = ans.size(); } } cout << u.size() << "\n"; for(auto [a, b] : u){ cout << a << " " << b << "\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...