Submission #231015

#	Time	Username	Problem	Language	Result	Execution time	Memory
231015		AlexLuchianov	Network (BOI15_net)	C++14	0 / 100	12 ms	12160 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';
  if(sol.size() % 2 == 1){
    cout << sol.back() << " " << root << '\n';
    sol.pop_back();
  }
  for(int i = 0; i < sol.size() / 2; i++)
    cout << sol[i] << " " << sol[i + 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++){
                  ~~^~~~~~~~~~~~~~~~
net.cpp: In function 'int main()':
net.cpp:51:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < sol.size() / 2; i++)
                  ~~^~~~~~~~~~~~~~~~

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