Submission #231016

#	Time	Username	Problem	Language	Result	Execution time	Memory
231016		AlexLuchianov	Network (BOI15_net)	C++14	100 / 100	529 ms	57852 KiB

net

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cmath>

using namespace std;

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 500000;
vector<int> g[1 + nmax];

vector<int> sol;

void dfs(int node, int parent){
  for(int h = 0; h < g[node].size(); h++){
    int to = g[node][h];
    if(to != parent)
      dfs(to, node);
  }
  if(g[node].size() == 1)
    sol.push_back(node);
}

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);

  int n;
  cin >> n;
  for(int i = 1;i < n; i++){
    int x, y;
    cin >> x >> y;
    g[x].push_back(y);
    g[y].push_back(x);
  }
  int root = 1;
  for(int i = 1;i <= n; i++)
    if(1 < g[i].size())
      root = i;
  dfs(root, 0);
  cout << (sol.size() + 1) / 2 << '\n';

  int d = sol.size() / 2;

  if(sol.size() % 2 == 1)
    cout << sol[d] << " " << root << '\n';

  for(int i = 0; i < d; i++)
    cout << sol[i] << " " << sol[i + d + sol.size() % 2] << '\n';

  return 0;
}

Compilation message (stderr)

net.cpp: In function 'void dfs(int, int)':
net.cpp:19:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int h = 0; h < g[node].size(); h++){
                  ~~^~~~~~~~~~~~~~~~

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