oj.uz

Submission #79548

# Submission time Handle Problem Language Result Execution time Memory
79548 2018-10-15T02:37:48 Z IOrtroiii Network (BOI15_net) C++14
0 / 100
 13 ms 12284 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 500005;

int n;
vector<int> g[N];
vector<int> leaves;

void dfs(int u,int p) {
   bool leaf = 1;
   for (int v : g[u]) if (v != p) {
      dfs(v, u); leaf = 0;
   }
   if (leaf) leaves.push_back(u);
}

int main() {
   ios_base::sync_with_stdio(false);
   cin >> n;
   for (int i = 1; i <= n - 1; ++i) {
      int u, v; cin >> u >> v;
      g[u].push_back(v), g[v].push_back(u);
   }
   int root = -1;
   for (int i = 1; i <= n; ++i) if (g[i].size() >= 2) {
      root = i; break;
   }
   dfs(root, -1);
   int sz = leaves.size();
   cout << (sz + 1) / 2 << '\n';
   if (sz & 1) {
      cout << root << ' ' << leaves[0] << '\n';
      for (int i = 1; i + i < sz; ++i) {
         cout << leaves[i] << ' ' << leaves[sz - i] << '\n';
      }
   }
   else {
      for (int i = 0; i + i < sz; ++i) {
         cout << leaves[i] << ' ' << leaves[sz - 1 - i] << '\n';
      }
   }
}

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12152 KB Output is correct
2 Incorrect 12 ms 12284 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 13 ms 12152 KB Output is correct
2 Incorrect 12 ms 12284 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 13 ms 12152 KB Output is correct
2 Incorrect 12 ms 12284 KB Breaking single line is causing network to disconnect.
3 Halted 0 ms 0 KB -