제출 #550825

#제출 시각아이디문제언어결과실행 시간메모리
550825BobonbushNetwork (BOI15_net)C++17
100 / 100
539 ms45384 KiB
#include <bits/stdc++.h> #define foreach for #define in : using namespace std; typedef long long ll; /* Konichiwa Konichiwa Ara ~~ ara Bob no taisuki - Shinobu Kocho * * * * * * * * * * * I love SHINOBU <3 <3 <3 * * * * * * * * * */ /* _________________________ Author : Bob15324 _________________________ */ template<class X , class Y> bool Minimize(X & x , Y y) { if(x == -1 || x >y) { x = y; return true; } return false; } template<class X , class Y> bool Maximize(X & x , Y y) { if( x < y) { x = y; return true; } return false; } /* End of templates. Let's see what do we have here */ const int N = 5e5+1; int n , deg[N] ; vector<int>Leaves; class GRAPH { private: vector<vector<int>>vertices; public : GRAPH(int _n) { vertices.resize(_n+1); } void AddEdge(int u ,int v) { vertices[u].push_back(v); vertices[v].push_back(u); } void DFS(int u ,int daddy) { if(deg[u] == 1) { Leaves.push_back(u); } foreach(int v in vertices[u]) { if(v == daddy) { continue; } DFS(v , u); } } }; int u ,v; int main() { ios_base :: sync_with_stdio(0);cin.tie(0); cin >> n; GRAPH graph(n); for(int i = 1; i <= n-1 ; i++) { cin >> u >> v; graph.AddEdge(u , v); deg[u]++; deg[v]++; } graph.DFS(1 , -1); cout << (((int)Leaves.size() + 1) >> 1) <<'\n' ; for(int i = 0 ; i <= ((int)Leaves.size() >> 1) - 1 ; i++) { cout << Leaves[i] << ' ' << Leaves[i + ((int)Leaves.size() >> 1 )] <<'\n'; } if(((int)Leaves.size() ) & 1) { cout << (int)Leaves[(int)Leaves.size()-1] << ' ' << (int)Leaves[((int)Leaves.size()) >> 1] <<'\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...