Submission #1243321

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243321		lopkus	Network (BOI15_net)	C++20	100 / 100	327 ms	52032 KiB

net

#include <bits/stdc++.h>

int main() {
  int n;
  std::cin >> n;
  std::vector<int> adj[n + 1];
  for(int i = 1; i < n; i++) {
    int u, v;
    std::cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  int timer = 1;
  std::vector<int> in(n + 1);
  std::function<void(int, int)> dfs = [&] (int v, int p) {
    in[v] = timer++;
    for(auto u : adj[v]) {
      if(u == p) {
        continue;
      }
      dfs(u, v);
    }
  };
  dfs(1, 0);
  std::vector<std::pair<int, int>> ans;
  std::vector<std::pair<int, int>> l;
  for(int i = 1; i <= n; i++) {
    if(adj[i].size() == 1) {
      l.push_back({in[i], i});
    }
  }
  std::sort(l.begin(), l.end());
  int L = l.size();
  for(int i = 0; i < l.size() && ans.size() < (L + 1) / 2; i++) {
    ans.push_back({l[i].second, l[(i + L / 2) % L].second});
  }
  std::cout << ans.size() << "\n";
  for(int i = 0; i < ans.size(); i++) {
    std::cout << ans[i].first << " " << ans[i].second << "\n";
  }
}

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