# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
24513 | 2017-06-09T15:36:37 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]; } } } bool comp(int x, int y) { return sub[x] > sub[y]; } void dfs(int x, int par) { if(deg[x] == 1) { nodes.push_back(x); } sort(g[x].begin(), g[x].end(), comp); 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); dfs(root, 0); printf("%d\n", (nodes.size() + 1) >> 1); int good = nodes.front(); while(nodes.size() > 1) { int p = nodes.front(); int q = nodes.back(); nodes.pop_front(); nodes.pop_back(); printf("%d %d\n", p, q); } if(!nodes.empty()) { printf("%d %d\n", good, nodes.front()); } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 17648 KB | Output is correct |
2 | Incorrect | 3 ms | 17648 KB | Breaking single line is causing network to disconnect. |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 17648 KB | Output is correct |
2 | Incorrect | 3 ms | 17648 KB | Breaking single line is causing network to disconnect. |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 17648 KB | Output is correct |
2 | Incorrect | 3 ms | 17648 KB | Breaking single line is causing network to disconnect. |
3 | Halted | 0 ms | 0 KB | - |