# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
305447 | 2020-09-23T08:16:19 Z | shahriarkhan | Network (BOI15_net) | C++14 | 11 ms | 12160 KB |
#include<bits/stdc++.h> using namespace std ; const int siz = 5e5 + 69 ; vector<int> adj[siz] ; int col[siz] ; void dfs(int s , int p) { for(int t : adj[s]) { if(t==p) continue ; dfs(t,s) ; col[t] = col[s] ; } } int main() { int n ; scanf("%d",&n) ; int deg[n+1] = {0} , mx = 0 , root = 0 ; for(int i = 1 ; i < n ; ++i) { int u , v ; scanf("%d%d",&u,&v) ; ++deg[u] , ++deg[v] ; mx = max(mx,max(deg[u],deg[v])) ; } for(int i = 1 ; i <= n ; ++i) { if(deg[i]==mx) { root = i ; break ; } } int cnt = 0 , cur = 1 ; for(int i : adj[root]) { col[i] = ++cnt ; dfs(i,root) ; } vector<pair<int,int> > ar ; for(int i = 1 ; i <= n ; ++i) { if(deg[i]==1) { ar.push_back({col[i],i}) ; } } int six = ar.size() ; sort(ar.begin(),ar.end()) ; if(six%2) { ar.push_back(ar[0]) ; ++six ; } printf("%d\n",(six+1)/2) ; for(int i = 0 ; i < six ; i += 2) { printf("%d %d\n",ar[i].second,ar[i+1].second) ; } return 0 ; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 12032 KB | Output is correct |
2 | Correct | 10 ms | 12032 KB | Output is correct |
3 | Correct | 11 ms | 12032 KB | Output is correct |
4 | Correct | 9 ms | 12032 KB | Output is correct |
5 | Correct | 10 ms | 12160 KB | Output is correct |
6 | Correct | 10 ms | 12032 KB | Output is correct |
7 | Correct | 11 ms | 12032 KB | Output is correct |
8 | Correct | 9 ms | 12032 KB | Output is correct |
9 | Correct | 9 ms | 12032 KB | Output is correct |
10 | Incorrect | 9 ms | 12160 KB | Breaking single line is causing network to disconnect. |
11 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 12032 KB | Output is correct |
2 | Correct | 10 ms | 12032 KB | Output is correct |
3 | Correct | 11 ms | 12032 KB | Output is correct |
4 | Correct | 9 ms | 12032 KB | Output is correct |
5 | Correct | 10 ms | 12160 KB | Output is correct |
6 | Correct | 10 ms | 12032 KB | Output is correct |
7 | Correct | 11 ms | 12032 KB | Output is correct |
8 | Correct | 9 ms | 12032 KB | Output is correct |
9 | Correct | 9 ms | 12032 KB | Output is correct |
10 | Incorrect | 9 ms | 12160 KB | Breaking single line is causing network to disconnect. |
11 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 12032 KB | Output is correct |
2 | Correct | 10 ms | 12032 KB | Output is correct |
3 | Correct | 11 ms | 12032 KB | Output is correct |
4 | Correct | 9 ms | 12032 KB | Output is correct |
5 | Correct | 10 ms | 12160 KB | Output is correct |
6 | Correct | 10 ms | 12032 KB | Output is correct |
7 | Correct | 11 ms | 12032 KB | Output is correct |
8 | Correct | 9 ms | 12032 KB | Output is correct |
9 | Correct | 9 ms | 12032 KB | Output is correct |
10 | Incorrect | 9 ms | 12160 KB | Breaking single line is causing network to disconnect. |
11 | Halted | 0 ms | 0 KB | - |