Submission #1243321

#TimeUsernameProblemLanguageResultExecution timeMemory
1243321lopkusNetwork (BOI15_net)C++20
100 / 100
327 ms52032 KiB
#include <bits/stdc++.h> int main() { int n; std::cin >> n; std::vector<int> adj[n + 1]; for(int i = 1; i < n; i++) { int u, v; std::cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } int timer = 1; std::vector<int> in(n + 1); std::function<void(int, int)> dfs = [&] (int v, int p) { in[v] = timer++; for(auto u : adj[v]) { if(u == p) { continue; } dfs(u, v); } }; dfs(1, 0); std::vector<std::pair<int, int>> ans; std::vector<std::pair<int, int>> l; for(int i = 1; i <= n; i++) { if(adj[i].size() == 1) { l.push_back({in[i], i}); } } std::sort(l.begin(), l.end()); int L = l.size(); for(int i = 0; i < l.size() && ans.size() < (L + 1) / 2; i++) { ans.push_back({l[i].second, l[(i + L / 2) % L].second}); } std::cout << ans.size() << "\n"; for(int i = 0; i < ans.size(); i++) { std::cout << ans[i].first << " " << ans[i].second << "\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...