Submission #476183

#	Time	Username	Problem	Language	Result	Execution time	Memory
476183		elgamalsalman	Network (BOI15_net)	C++14	100 / 100	476 ms	47428 KiB

net

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second

typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

int timer, n;
vvi adj;
vii leaves;

void dfs(int u, int p) {
  //cerr << "// dfs(" << u << ", " << p << ")\n";
  timer++;
  if (adj[u].size() == 1) leaves.push_back({timer, u});
  for (int v : adj[u]) if (v != p) dfs(v, u);
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  cin >> n;
  adj.assign(n + 20, vi());
  for (int i = 0; i < n - 1; i++) {
    int a, b;
    cin >> a >> b;
    a--; b--;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }

  dfs(0, -1);
  sort(leaves.begin(), leaves.end());
  
  //cerr << "// leaves :";
  //for (ii leaf : leaves) cerr << " {" << leaf.fi << ", " << leaf.se << '}';
  //cerr << '\n';

  int leafCount = leaves.size();
  int edgeCount = (leaves.size() + 1) / 2;
  cout << edgeCount << '\n';

  for (int i = 0; i < edgeCount; i++) {
    int j = edgeCount + i;
    if (i == j) j = 0;
    cout << leaves[i].se + 1 << ' ' << leaves[j].se + 1 << '\n';
  }
}

Compilation message (stderr)

net.cpp: In function 'int main()':
net.cpp:45:7: warning: unused variable 'leafCount' [-Wunused-variable]
   45 |   int leafCount = leaves.size();
      |       ^~~~~~~~~

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