# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
905898 | 2024-01-13T06:54:51 Z | dsyz | Network (BOI15_net) | C++17 | 4 ms | 12376 KB |
#include <bits/stdc++.h> using namespace std; using ll = long long; #define MAXN (500005) ll N, connectto1 = -1; vector<ll> v[MAXN]; bool leaf[MAXN]; void dfs(ll x,ll p){ ll children = 0; ll leafchildren = 0; for(auto u : v[x]){ if(u != p){ dfs(u,x); leafchildren += leaf[u]; if(leafchildren >= 2) connectto1 = u; children++; } } if(children == 0){ leaf[x] = 1; } } int main() { ios_base::sync_with_stdio(false);cin.tie(0); cin>>N; for(ll i = 0;i < N - 1;i++){ ll a,b; cin>>a>>b; a--, b--; v[a].push_back(b); v[b].push_back(a); } dfs(0,-1); vector<ll> ans; for(ll i = 0;i < N;i++){ if(leaf[i] && i != connectto1){ ans.push_back(i + 1); } } cout<<ans.size() - 1<<'\n'; cout<<1<<" "<<connectto1<<'\n'; for(ll i = 1;i < ans.size();i++){ cout<<ans[i - 1]<<" "<<ans[i]<<'\n'; } }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 4 ms | 12376 KB | Invalid number of links. |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 4 ms | 12376 KB | Invalid number of links. |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 4 ms | 12376 KB | Invalid number of links. |
2 | Halted | 0 ms | 0 KB | - |