Submission #1213428

#TimeUsernameProblemLanguageResultExecution timeMemory
1213428minhpkNetwork (BOI15_net)C++20
0 / 100
13 ms23872 KiB
#include <bits/stdc++.h> #define int long long using namespace std; int a; vector<int> z[1000005]; vector<int> v; int sta[1000005]; int tour; void dfs(int i, int parent) { sta[i] = ++tour; for (auto p : z[i]) { if (p == parent) continue; dfs(p, i); } } bool cmp(int A, int B) { return sta[A] < sta[B]; } signed main() { ios::sync_with_stdio(false); cin.tie(NULL); cin >> a; for (int i = 1; i < a; i++) { int x, y; cin >> x >> y; z[x].push_back(y); z[y].push_back(x); } for (int i = 1; i <= a; i++) { if (z[i].size() == 1) { v.push_back(i); } } dfs(1, 0); int k = v.size(); cout << (k + 1) / 2 << "\n"; sort(v.begin(), v.end(), cmp); if (k % 2 == 1) { v.push_back(v[0]); } for (int i = 0; i < v.size(); i += 2) { cout << v[i] << " " << v[i + 1] << "\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...