# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
24527 | 2017-06-09T19:34:11 Z | Bruteforceman | Network (BOI15_net) | C++11 | 3 ms | 17652 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 leave = sub[root]; int centre = centroid(root, 0, half); dfs(centre, 0); leaf(centre, 0); assert(deg[centre] != 1); for(auto i : g[centre]) { if(sub[i] > half) { assert(false); } } assert(leave % 2 == 0); printf("%d\n", half); for(int i = 0; i + half < leave; i++) { printf("%d %d\n", nodes[i], nodes[i + half]); } if(leave & 1) { printf("%d %d\n", nodes[half], nodes.back()); } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 17648 KB | Output is correct |
2 | Correct | 0 ms | 17648 KB | Output is correct |
3 | Correct | 3 ms | 17648 KB | Output is correct |
4 | Runtime error | 0 ms | 17652 KB | Execution killed because of forbidden syscall gettid (186) |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 17648 KB | Output is correct |
2 | Correct | 0 ms | 17648 KB | Output is correct |
3 | Correct | 3 ms | 17648 KB | Output is correct |
4 | Runtime error | 0 ms | 17652 KB | Execution killed because of forbidden syscall gettid (186) |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 17648 KB | Output is correct |
2 | Correct | 0 ms | 17648 KB | Output is correct |
3 | Correct | 3 ms | 17648 KB | Output is correct |
4 | Runtime error | 0 ms | 17652 KB | Execution killed because of forbidden syscall gettid (186) |
5 | Halted | 0 ms | 0 KB | - |