Submission #755837

#TimeUsernameProblemLanguageResultExecution timeMemory
755837JellyTheOctopusNetwork (BOI15_net)C++17
0 / 100
7 ms12024 KiB
// Baltic Olympiad in Informatics 2015 Day 1 Problem 3 // Network // https://oj.uz/problem/view/BOI15_net #include <bits/stdc++.h> using namespace std; int N; vector<int> adjList[500001]; vector<int> leaf; void DFS(int node, int parent) { int numOfVertices = 0; for (auto child: adjList[node]) { numOfVertices++; if (child != parent) { DFS(child, node); } } if (numOfVertices == 1) { leaf.push_back(node); } } int main() { cin >> N; for (int i = 1; i < N; i++) { int u, v; cin >> u >> v; adjList[u].push_back(v); adjList[v].push_back(u); } DFS(1, -1); int k = (int)leaf.size(); if (k % 2 == 0) { cout << k/2 << "\n"; for (int i = 0; i < k/2; i++) { cout << leaf[i] << " " << leaf[i+k/2] << "\n"; } } else { cout << k/2+1 << "\n"; for (int i = 0; i < k/2; i++) { cout << leaf[i] << " " << leaf[i+k/2] << "\n"; } cout << leaf[k/2] << " " << 1 << "\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...