# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
905904 | 2024-01-13T07:00:20 Z | dsyz | Network (BOI15_net) | C++17 | 4 ms | 12636 KB |
#include <bits/stdc++.h> using namespace std; using ll = long long; #define MAXN (500005) ll N, connectto1 = -1, cnt = 0; ll pre[MAXN]; vector<ll> v[MAXN]; bool leaf[MAXN]; void dfs(ll x,ll p){ pre[x] = cnt++; 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<pair<ll,ll> > ans; for(ll i = 0;i < N;i++){ if(leaf[i] && i != connectto1){ ans.push_back({pre[i],i}); } } sort(ans.begin(),ans.end()); cout<<ans.size() - 1 + 1<<'\n'; cout<<1<<" "<<connectto1 + 1<<'\n'; for(ll i = 1;i < ans.size();i++){ cout<<ans[i - 1].second + 1<<" "<<ans[i].second + 1<<'\n'; } }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 4 ms | 12636 KB | Breaking single line is causing network to disconnect. |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 4 ms | 12636 KB | Breaking single line is causing network to disconnect. |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 4 ms | 12636 KB | Breaking single line is causing network to disconnect. |
2 | Halted | 0 ms | 0 KB | - |