Submission #406297

#	Time	Username	Problem	Language	Result	Execution time	Memory
406297		victoriad	Network (BOI15_net)	C++14	100 / 100	497 ms	56260 KiB

net

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <utility>
#include <queue>
#include <map>
#include <iomanip>
using namespace std;

 void dfs(vector<int>&nodos,vector<vector<int> >&g,int & con,int actu,vector<bool>&v){
   v[actu]=true;
   if(g[actu].size()==1){
     nodos.push_back(actu);
     con++;
   }
   for(int c:g[actu]){
     if(!v[c]){
       dfs(nodos,g,con,c,v);
     }
   }
 }
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int n,a,b;
cin>>n;
vector<vector<int> >g(n);
for(int i=0;i<n-1;i++){
cin>>a>>b;
a--;
b--;
g[a].push_back(b);
g[b].push_back(a);
}
vector<bool>v(n,false);
vector<int>nodos;
int con=0;
dfs(nodos,g,con,0,v);
if(con&1){
  cout<<con/2+1<<"\n";
}
else{
  cout<<con/2<<"\n";
}
for(int i=0;i<con/2;i++){
  cout<<nodos[i]+1<<" "<<nodos[i+(con+1)/2]+1<<"\n";
}
if(con&1){
  cout<<nodos[con/2]+1<<" ";
  int p=g[con/2][0];
  for(int i=0;i<n;i++){
    if(i!=p && i!=nodos[con/2]){
      cout<<i+1<<"\n";
      break;
    }
  }
}
  return 0;
}

• Subtask 1: 18 / 18
• Subtask 2: 45 / 45
• Subtask 3: 37 / 37