oj.uz

Submission #476182

# Submission time Handle Problem Language Result Execution time Memory
476182 2021-09-25T08:49:56 Z elgamalsalman Network (BOI15_net) C++14
0 / 100
 1 ms 312 KB 
#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 = leafCount - i - 1;
    if (i == j) j = 0;
    cout << leaves[i].se + 1 << ' ' << leaves[j].se + 1 << '\n';
  }
}

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Incorrect 0 ms 204 KB Breaking single line is causing network to disconnect.
3 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Incorrect 0 ms 204 KB Breaking single line is causing network to disconnect.
3 Halted 0 ms 0 KB -

Subtask #3
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Incorrect 0 ms 204 KB Breaking single line is causing network to disconnect.
3 Halted 0 ms 0 KB -