Submission #564326

#	Time	Username	Problem	Language	Result	Execution time	Memory
564326		SSRS	Network (BOI15_net)	C++14	100 / 100	867 ms	56264 KiB

net

#include <bits/stdc++.h>
using namespace std;
void dfs(vector<vector<int>> &E	, vector<bool> &used, vector<int> &L, int v = 0){
  if (E[v].size() == 1){
    L.push_back(v);
  }
  for (int w : E[v]){
    if (!used[w]){
      used[w] = true;
      dfs(E, used, L, w);
    }
  }
}
int main(){
  int n;
  cin >> n;
  vector<vector<int>> E(n);
  for (int i = 0; i < n - 1; i++){
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    E[a].push_back(b);
    E[b].push_back(a);
  }
  vector<bool> used(n, false);
  used[0] = true;
  vector<int> L;
  dfs(E, used, L);
  int cnt = L.size();
  int k = (cnt + 1) / 2;
  cout << k << endl;
  for (int i = 0; i < k; i++){
    cout << L[i] + 1 << ' ' << L[(i + k) % cnt] + 1 << endl;
  }
}

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