Submission #1265190

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265190		rtri	Network (BOI15_net)	C++20	0 / 100	0 ms	328 KiB

net

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

vector<vector<int>> adj;

vector<bool> is_leaf;

pair<int, int> dfs(int u, int p = -1, int d = 0) {
  if (is_leaf[u] && p != -1) {
    return {d, u};
  }

  int bestd = -1, besti = -1;
  for (int v : adj[u])
    if (v != p) {
      auto [subd, subi] = dfs(v, u, d + 1);
      if (subd > bestd) {
        bestd = subd;
        besti = subi;
      }
    }

  return {besti, bestd};
}

int main() {
  int k;
  cin >> k;
  adj.resize(k);
  for (int i = 0; i < k - 1; i++) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }

  vector<int> leafs;
  is_leaf.resize(k);
  for (int i = 0; i < k; i++)
    if (adj[i].size() <= 1) {
      leafs.push_back(i);
      is_leaf[i] = 1;
    }

  vector<pair<int, int>> ans;

  for (int i = 0; i < leafs.size() / 2; i++) {
    int best_dist = -1;
    int best_leaf = -1, best_other = -1;
    for (int leaf : leafs)
      if (is_leaf[leaf]) {
        auto [dist, other] = dfs(leaf);
        if (best_dist < dist) {
          best_dist = dist;
          best_leaf = leaf;
          best_other = other;
        }
      }

    is_leaf[best_leaf] = 0;
    is_leaf[best_other] = 0;
    ans.push_back({best_leaf, best_other});
  }

  if (leafs.size() % 2 == 1) {
    int extra_leaf = -1;
    int other_leaf = 0;
    for (int i = 0; i < leafs.size(); i++)
      if (is_leaf[leafs[i]])
        extra_leaf = leafs[i];
      else
        other_leaf = leafs[i];
    ans.push_back({other_leaf, extra_leaf});
  }

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

  return 0;
}

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