Submission #732076

#	Time	Username	Problem	Language	Result	Execution time	Memory
732076		ollel	Network (BOI15_net)	C++14	100 / 100	944 ms	72916 KiB

net

#include <bits/stdc++.h>
using namespace std;
#include <iostream>

typedef vector<int> vi;
typedef vector<vi> vvi;

#define pb push_back
#define rep(i,a,b) for(int i = a; i < b; i++)

int n;
vvi g;
vi leaf;
int total_leafs;
vvi groups;
vi par;

void dfs(int x, int p) {
  par[x] = p;
  for (auto y : g[x]) {
    if (y == p) continue;

    dfs(y, x);
    leaf[x] += leaf[y];
  }
}

void dfs3(int x, int p) {
  par[x] = p;
  for (auto y : g[x]) if (y != p) dfs3(y, x);
}

bool test(int r) {
  for (auto y : g[r]) if (par[r] != y) if (leaf[y] > total_leafs / 2) return false;
  if (total_leafs - leaf[r] > total_leafs / 2) return false;
  return true;
}

void dfs2(int x, int p, vi & group) {
  for (auto y : g[x]) {
    if (y == p) continue;
    dfs2(y, x, group);
  }
  if (g[x].size() == 1) group.pb(x);
}

int main() {
  cin >> n;
  par.resize(n);
  if (n == 2) {
    cout << 1 << "\n" << 1 << " " << 2 << endl;
    exit(0);
  }

  g.resize(n);
  rep(i,0,n-1) {
    int a, b;
    cin >> a >> b;
    a--;b--;
    g[a].pb(b);
    g[b].pb(a);
  }

  leaf.assign(n, 0);
  rep(i,0,n) if (g[i].size() == 1) leaf[i] = 1;

  int root = 0;
  while (leaf[root] > 0) root++;
  dfs(root, -1);
  total_leafs = leaf[root];

  while (!test(root)) root++;

  for (auto y : g[root]) {
    vi group;
    dfs2(y, root, group);
    groups.pb(group);
  }


  priority_queue<pair<int,int>> pq;
  int I = 0;
  for (auto & gr : groups) {
    pq.push({gr.size(), I});
    I++;
  }
  vector<pair<int,int>> ans;

  while (true) {
    pair<int,int> a = pq.top(); pq.pop();
    pair<int,int> b = pq.top(); pq.pop();

    if (a.first == 0) break;
    if (b.first == 0) {
      ans.pb({groups[a.second][0], root});
      break;
    }
    ans.pb({groups[a.second][a.first-1], groups[b.second][b.first-1]});
    pq.push({a.first-1, a.second});
    pq.push({b.first-1, b.second});
  }

  cout << ans.size() << endl;
  for (auto [a, b] : ans) {
    cout << a + 1 << " " << b + 1 << endl;
  }

}

Compilation message (stderr)

net.cpp: In function 'int main()':
net.cpp:106:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  106 |   for (auto [a, b] : ans) {
      |             ^

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