# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
79562 | 2018-10-15T03:10:57 Z | Flying_dragon_02 | Network (BOI15_net) | C++14 | 13 ms | 12300 KB |
#include <bits/stdc++.h> using namespace std; #define fi first #define se second #define pb push_back #define mp make_pair typedef pair<int, int> ii; const int N = 5e5 + 5; int n, dp[N]; bool vis[N]; vector<int> graph[N]; vector<int> ans; void dfs(int u, int p) { vis[u] = 1; int cnt = 0; for(int i = 0; i < graph[u].size(); i++) { int v = graph[u][i]; if(!vis[v] && v != p) { dfs(v, u); cnt++; } } if(!cnt) ans.pb(u); } int main() { cin.tie(0), ios::sync_with_stdio(0); cin >> n; for(int i = 1; i <= n - 1; i++) { int u, v; cin >> u >> v; graph[u].pb(v); graph[v].pb(u); } int cen; for(int i = 1; i <= n; i++) { if(graph[i].size() > 1) cen = i; } dfs(cen, cen); if(ans.size() % 2 == 0) { cout << ans.size() / 2 << "\n"; for(int i = 0; i < ans.size() / 2; i++) { cout << ans[i] << " " << ans[i + ans.size() / 2] << "\n"; } } else { cout << ans.size() / 2 + 1 << "\n"; cout << ans[ans.size() / 2 + 1] << " " << cen << "\n"; for(int i = 0; i < ans.size() / 2; i++) { cout << ans[i] << " " << ans[i + ans.size() / 2 + 1] << "\n"; } } }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 13 ms | 12024 KB | Output is correct |
2 | Correct | 12 ms | 12300 KB | Output is correct |
3 | Correct | 12 ms | 12300 KB | Output is correct |
4 | Incorrect | 12 ms | 12300 KB | Breaking single line is causing network to disconnect. |
5 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 13 ms | 12024 KB | Output is correct |
2 | Correct | 12 ms | 12300 KB | Output is correct |
3 | Correct | 12 ms | 12300 KB | Output is correct |
4 | Incorrect | 12 ms | 12300 KB | Breaking single line is causing network to disconnect. |
5 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 13 ms | 12024 KB | Output is correct |
2 | Correct | 12 ms | 12300 KB | Output is correct |
3 | Correct | 12 ms | 12300 KB | Output is correct |
4 | Incorrect | 12 ms | 12300 KB | Breaking single line is causing network to disconnect. |
5 | Halted | 0 ms | 0 KB | - |