# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
705323 | 2023-03-04T01:02:13 Z | anha3k25cvp | Network (BOI15_net) | C++14 | 0 ms | 320 KB |
#include <bits/stdc++.h> #define ll long long #define dl double #define st first #define nd second #define II pair <int, int> using namespace std; const int N = 1 + 1e5; const int inf = 7 + 1e9; vector <int> h; vector <vector <int>> g; void dfs(int u) { for (int v : g[u]) if (!h[v]) { h[v] = h[u] + 1; dfs(v); } } int main() { #define TASKNAME "net" ios_base :: sync_with_stdio (0); cin.tie (0); if ( fopen( TASKNAME".inp", "r" ) ) { freopen( TASKNAME".inp", "r", stdin ); freopen( TASKNAME".out", "w", stdout ); } int n; cin >> n; g.resize(n + 1); for (int i = 1; i < n; i ++) { int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } h.assign(n + 1, 0); h[1] = 1; dfs(1); vector <II> q; for (int i = 1; i <= n; i ++) if (g[i].size() == 1) q.push_back({h[i], i}); sort(q.begin(), q.end()); int m = q.size(); vector <II> ans; for (int i = 0; i < m / 2; i ++) ans.push_back({q[i].nd, q[(m / 2) + i].nd}); if (m & 1) ans.push_back({q[0].nd, q.back().nd}); cout << ans.size() << '\n'; for (auto z : ans) cout << z.st << ' ' << z.nd << '\n'; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Incorrect | 0 ms | 320 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 | 212 KB | Output is correct |
2 | Incorrect | 0 ms | 320 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 | 212 KB | Output is correct |
2 | Incorrect | 0 ms | 320 KB | Breaking single line is causing network to disconnect. |
3 | Halted | 0 ms | 0 KB | - |