Submission #320883

#TimeUsernameProblemLanguageResultExecution timeMemory
320883gustasonNetwork (BOI15_net)C++14
18 / 100
10 ms12268 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const int maxN = 500005; vector<int> adj[maxN], leafs; void dfs(int v, int par) { if (adj[v].size() == 1) { leafs.push_back(v); } for(int u : adj[v]) { if (u != par) { dfs(u, v); } } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; for(int i = 0; i < n-1; i++) { int a, b; cin >> a >> b; adj[a].push_back(b); adj[b].push_back(a); } dfs(1, -1); int ls = leafs.size(); if (ls % 2 == 0) { cout << ls / 2 << "\n"; for(int i = 0; i < ls/2; i++) { cout << leafs[i] << " " << leafs[ls/2+i] << "\n"; } } else { cout << ls / 2 + 1 << "\n"; for(int i = 0; i < ls/2; i++) { cout << leafs[i] << " " << leafs[ls/2+i] << "\n"; } cout << leafs.back() << " " << 1; } return 0; } //~ check for overflows
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...