# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
605110 | 2022-07-25T13:06:02 Z | tamthegod | Network (BOI15_net) | C++14 | 16 ms | 23820 KB |
#include<bits/stdc++.h> #define int long long #define pb push_back #define fi first #define se second using namespace std; using ll = long long; using ld = long double; using ull = unsigned long long; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int maxN = 1e6 + 5; const int mod = 1e9 + 7; const ll oo = 1e18; int n; vector<int> adj[maxN]; int depth[maxN]; void ReadInput() { cin >> n; for(int i=1; i<n; i++) { int u, v; cin >> u >> v; adj[u].pb(v); adj[v].pb(u); } } void dfs(int u, int par) { for(int v : adj[u]) { if(v == par) continue; depth[v] = depth[u] + 1; dfs(v, u); } } void Solve() { dfs(1, 0); vector<int> leaf; for(int i=1; i<=n; i++) { if(adj[i].size() == 1) leaf.pb(i); } int l = 0, step = leaf.size() / 2; if(leaf.size() % 2 == 0) { cout << leaf.size() / 2 << '\n'; while(l + step < leaf.size()) { cout << leaf[l] << " " << leaf[l + step] << '\n'; l++; } return; } leaf.pb(leaf[0]); step++; cout << leaf.size() / 2 << '\n'; while(l + step < leaf.size()) { cout << leaf[l] << " " << leaf[l + step] << '\n'; l++; } } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); ReadInput(); Solve(); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 14 ms | 23712 KB | Output is correct |
2 | Correct | 12 ms | 23748 KB | Output is correct |
3 | Correct | 15 ms | 23764 KB | Output is correct |
4 | Correct | 15 ms | 23808 KB | Output is correct |
5 | Correct | 15 ms | 23732 KB | Output is correct |
6 | Correct | 16 ms | 23820 KB | Output is correct |
7 | Correct | 14 ms | 23764 KB | Output is correct |
8 | Correct | 14 ms | 23764 KB | Output is correct |
9 | Correct | 13 ms | 23692 KB | Output is correct |
10 | Correct | 16 ms | 23808 KB | Output is correct |
11 | Correct | 15 ms | 23696 KB | Output is correct |
12 | Incorrect | 13 ms | 23764 KB | Breaking single line is causing network to disconnect. |
13 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 14 ms | 23712 KB | Output is correct |
2 | Correct | 12 ms | 23748 KB | Output is correct |
3 | Correct | 15 ms | 23764 KB | Output is correct |
4 | Correct | 15 ms | 23808 KB | Output is correct |
5 | Correct | 15 ms | 23732 KB | Output is correct |
6 | Correct | 16 ms | 23820 KB | Output is correct |
7 | Correct | 14 ms | 23764 KB | Output is correct |
8 | Correct | 14 ms | 23764 KB | Output is correct |
9 | Correct | 13 ms | 23692 KB | Output is correct |
10 | Correct | 16 ms | 23808 KB | Output is correct |
11 | Correct | 15 ms | 23696 KB | Output is correct |
12 | Incorrect | 13 ms | 23764 KB | Breaking single line is causing network to disconnect. |
13 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 14 ms | 23712 KB | Output is correct |
2 | Correct | 12 ms | 23748 KB | Output is correct |
3 | Correct | 15 ms | 23764 KB | Output is correct |
4 | Correct | 15 ms | 23808 KB | Output is correct |
5 | Correct | 15 ms | 23732 KB | Output is correct |
6 | Correct | 16 ms | 23820 KB | Output is correct |
7 | Correct | 14 ms | 23764 KB | Output is correct |
8 | Correct | 14 ms | 23764 KB | Output is correct |
9 | Correct | 13 ms | 23692 KB | Output is correct |
10 | Correct | 16 ms | 23808 KB | Output is correct |
11 | Correct | 15 ms | 23696 KB | Output is correct |
12 | Incorrect | 13 ms | 23764 KB | Breaking single line is causing network to disconnect. |
13 | Halted | 0 ms | 0 KB | - |