# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
672872 | 2022-12-18T17:56:29 Z | iosif_andrei_ | Network (BOI15_net) | C++14 | 8 ms | 11988 KB |
#include <bits/stdc++.h> using namespace std; int n, h[500001]; vector <int> g[500001]; void dfs(int nod, int lvl) { h[nod] = lvl; for (auto& i : g[nod]) if (!h[i]) dfs(i, lvl + 1); } struct nod { int key; bool operator < (nod aux) { return h[key] < h[aux.key]; } }; vector <nod> v; int main() { cin >> n; for (int i = 1; i < n; i++) { int x, y; cin >> x >> y; g[x].push_back(y); g[y].push_back(x); } dfs(1, 1); for (int i = 1; i <= n; i++) if (g[i].size() == 1) v.push_back({ i }); cout << (v.size() + 1) / 2 << '\n'; sort(v.begin(), v.end()); int i = 0, j = v.size() - 1; if (v.size() % 2) { int i = 0, j = v.size() / 2; while (i < v.size() / 2) { cout << v[i].key << ' ' << v[j].key << '\n'; i++, j++; } int aux = v.back().key; if (g[aux][0] == 1) cout << aux << ' ' << 2; else cout << aux << ' ' << 1; } else { int i = 0, j = v.size() / 2; while (i < v.size() / 2) { cout << v[i].key << ' ' << v[j].key << '\n'; i++, j++; } } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 11988 KB | Output is correct |
2 | Incorrect | 6 ms | 11988 KB | Breaking single line is causing network to disconnect. |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 11988 KB | Output is correct |
2 | Incorrect | 6 ms | 11988 KB | Breaking single line is causing network to disconnect. |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 11988 KB | Output is correct |
2 | Incorrect | 6 ms | 11988 KB | Breaking single line is causing network to disconnect. |
3 | Halted | 0 ms | 0 KB | - |