# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
923267 | 2024-02-07T04:22:19 Z | Aiperiii | Network (BOI15_net) | C++14 | 4 ms | 13872 KB |
#include <bits/stdc++.h> #define int long long #define ff first #define ss second #define pb push_back #define all(x) x.begin(),x.end() using namespace std; const int N=5e5+5; vector <int> g[N]; int d[N]; void dfs(int v,int p){ for(auto to : g[v]){ if(to!=p){ d[to]=d[v]+1; dfs(to,v); } } } signed main(){ ios_base::sync_with_stdio(); cin.tie(0);cout.tie(0); int n;cin>>n; for(int i=0;i<n-1;i++){ int u,v; cin>>u>>v; g[u].pb(v); g[v].pb(u); } int root=1; for(int i=1;i<=n;i++){ if(g[i].size()==1){ root=i; } } //cout<<root<<"\n"; dfs(root,0); vector <pair <int,int> > v; for(int i=1;i<=n;i++){ if(g[i].size()==1 && i!=root)v.pb({d[i],i}); } sort(all(v)); //cout<<v.size()<<"\n"; cout<<v.size()/2+1<<"\n"; for(int i=0;i<v.size()-1;i+=2){ cout<<v[i].ss<<" "<<v[i+1].ss<<"\n"; } cout<<v.back().ss<<" "<<root<<"\n"; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 13660 KB | Output is correct |
2 | Correct | 4 ms | 13868 KB | Output is correct |
3 | Correct | 3 ms | 13872 KB | Output is correct |
4 | Correct | 4 ms | 13660 KB | Output is correct |
5 | Correct | 3 ms | 13660 KB | Output is correct |
6 | Correct | 3 ms | 13660 KB | Output is correct |
7 | Correct | 3 ms | 13660 KB | Output is correct |
8 | Correct | 3 ms | 13660 KB | Output is correct |
9 | Correct | 3 ms | 13660 KB | Output is correct |
10 | Correct | 3 ms | 13660 KB | Output is correct |
11 | Correct | 3 ms | 13660 KB | Output is correct |
12 | Correct | 3 ms | 13660 KB | Output is correct |
13 | Correct | 4 ms | 13660 KB | Output is correct |
14 | Correct | 3 ms | 13656 KB | Output is correct |
15 | Correct | 3 ms | 13660 KB | Output is correct |
16 | Correct | 3 ms | 13680 KB | Output is correct |
17 | Correct | 3 ms | 13660 KB | Output is correct |
18 | Incorrect | 3 ms | 13656 KB | Breaking single line is causing network to disconnect. |
19 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 13660 KB | Output is correct |
2 | Correct | 4 ms | 13868 KB | Output is correct |
3 | Correct | 3 ms | 13872 KB | Output is correct |
4 | Correct | 4 ms | 13660 KB | Output is correct |
5 | Correct | 3 ms | 13660 KB | Output is correct |
6 | Correct | 3 ms | 13660 KB | Output is correct |
7 | Correct | 3 ms | 13660 KB | Output is correct |
8 | Correct | 3 ms | 13660 KB | Output is correct |
9 | Correct | 3 ms | 13660 KB | Output is correct |
10 | Correct | 3 ms | 13660 KB | Output is correct |
11 | Correct | 3 ms | 13660 KB | Output is correct |
12 | Correct | 3 ms | 13660 KB | Output is correct |
13 | Correct | 4 ms | 13660 KB | Output is correct |
14 | Correct | 3 ms | 13656 KB | Output is correct |
15 | Correct | 3 ms | 13660 KB | Output is correct |
16 | Correct | 3 ms | 13680 KB | Output is correct |
17 | Correct | 3 ms | 13660 KB | Output is correct |
18 | Incorrect | 3 ms | 13656 KB | Breaking single line is causing network to disconnect. |
19 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 13660 KB | Output is correct |
2 | Correct | 4 ms | 13868 KB | Output is correct |
3 | Correct | 3 ms | 13872 KB | Output is correct |
4 | Correct | 4 ms | 13660 KB | Output is correct |
5 | Correct | 3 ms | 13660 KB | Output is correct |
6 | Correct | 3 ms | 13660 KB | Output is correct |
7 | Correct | 3 ms | 13660 KB | Output is correct |
8 | Correct | 3 ms | 13660 KB | Output is correct |
9 | Correct | 3 ms | 13660 KB | Output is correct |
10 | Correct | 3 ms | 13660 KB | Output is correct |
11 | Correct | 3 ms | 13660 KB | Output is correct |
12 | Correct | 3 ms | 13660 KB | Output is correct |
13 | Correct | 4 ms | 13660 KB | Output is correct |
14 | Correct | 3 ms | 13656 KB | Output is correct |
15 | Correct | 3 ms | 13660 KB | Output is correct |
16 | Correct | 3 ms | 13680 KB | Output is correct |
17 | Correct | 3 ms | 13660 KB | Output is correct |
18 | Incorrect | 3 ms | 13656 KB | Breaking single line is causing network to disconnect. |
19 | Halted | 0 ms | 0 KB | - |