# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
24514 | 2017-06-09T16:20:43 Z | Bruteforceman | Network (BOI15_net) | C++11 | 3 ms | 17648 KB |
#include "bits/stdc++.h" using namespace std; int deg[500010]; deque <int> nodes; vector <int> g[500010]; int sub[500010]; void leaf(int x, int par) { if(deg[x] == 1) sub[x] = 1; else sub[x] = 0; for(auto i : g[x]) { if(i - par) { leaf(i, x); sub[x] += sub[i]; } } } int centroid(int x, int par, int range) { for(auto i : g[x]) { if(i - par) { if(sub[i] > range) { return centroid(i, x, range); } } } return x; } void dfs(int x, int par) { if(deg[x] == 1) { nodes.push_back(x); } for(auto i : g[x]) { if(i - par) { dfs(i, x); } } } int main(int argc, char const *argv[]) { int n; scanf("%d", &n); for(int i = 1; i < n; i++) { int p, q; scanf("%d %d", &p, &q); ++deg[p]; ++deg[q]; g[p].push_back(q); g[q].push_back(p); } int root = 0; for(int i = 1; i <= n; i++) { if(deg[i] != 1) { root = i; break; } } leaf(root, 0); int half = (sub[root] + 1) >> 1; int centre = centroid(root, 0, half); dfs(centre, 0); printf("%d\n", half); for(int i = 0; i + half < sub[root]; i++) { printf("%d %d\n", nodes[i], nodes[i + half]); } if(sub[root] & 1) { printf("%d %d\n", nodes[half], nodes.back()); } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 17648 KB | Output is correct |
2 | Correct | 3 ms | 17648 KB | Output is correct |
3 | Correct | 0 ms | 17648 KB | Output is correct |
4 | Incorrect | 3 ms | 17648 KB | Breaking single line is causing network to disconnect. |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 17648 KB | Output is correct |
2 | Correct | 3 ms | 17648 KB | Output is correct |
3 | Correct | 0 ms | 17648 KB | Output is correct |
4 | Incorrect | 3 ms | 17648 KB | Breaking single line is causing network to disconnect. |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 17648 KB | Output is correct |
2 | Correct | 3 ms | 17648 KB | Output is correct |
3 | Correct | 0 ms | 17648 KB | Output is correct |
4 | Incorrect | 3 ms | 17648 KB | Breaking single line is causing network to disconnect. |
5 | Halted | 0 ms | 0 KB | - |