Submission #1265186

#TimeUsernameProblemLanguageResultExecution timeMemory
1265186rtriNetwork (BOI15_net)C++20
0 / 100
0 ms328 KiB
#include <bits/stdc++.h> using namespace std; vector<vector<int>> adj; vector<bool> is_leaf; pair<int, int> dfs(int u, int p = -1, int d = 0) { if (is_leaf[u] && p != -1) { return {d, u}; } int bestd = -1, besti = -1; for (int v : adj[u]) if (v != p) { auto [subd, subi] = dfs(v, u, d + 1); if (subd > bestd) { bestd = subd; besti = subi; } } return {besti, bestd}; } int main() { int k; cin >> k; adj.resize(k); for (int i = 0; i < k - 1; i++) { int a, b; cin >> a >> b; a--; b--; adj[a].push_back(b); adj[b].push_back(a); } vector<int> leafs; is_leaf.resize(k); for (int i = 0; i < k; i++) if (adj[i].size() <= 1) { leafs.push_back(i); is_leaf[i] = 1; } vector<pair<int, int>> ans; int idx = 0; for (int i = 0; i < leafs.size() / 2; i++) { while (!is_leaf[leafs[idx]]) idx++; auto [_, other] = dfs(leafs[idx]); is_leaf[other] = 0; is_leaf[leafs[idx]] = 0; ans.push_back({leafs[idx], other}); idx++; } if (leafs.size() % 2 == 1) { int extra_leaf = -1; for (int i = 0; i < leafs.size(); i++) if (is_leaf[leafs[i]]) extra_leaf = leafs[i]; ans.push_back({0, extra_leaf}); } cout << ans.size() << "\n"; for (auto [a, b] : ans) { cout << a + 1 << " " << b + 1 << "\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...