# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
305450 | 2020-09-23T08:22:40 Z | shahriarkhan | Network (BOI15_net) | C++14 | 11 ms | 12032 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] ; adj[u].push_back(v) ; adj[v].push_back(u) ; 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 , vis[n+1] = {0} , vi[n+1] = {0} ; for(int i : adj[root]) { col[i] = ++cnt ; dfs(i,root) ; } vector<int> ans ; for(int i = 1 ; i <= n ; ++i) { if(deg[i]==1) { if(!vis[col[i]]) { vi[i] = 1 ; vis[col[i]] = 1 ; ans.push_back(i) ; } } } int p = ans.size() ; if(p%2) { for(int i = 1 ; i <= n ; ++i) { if(deg[i]==1) { if(!vi[i]) { vi[i] = 1 ; ans.push_back(i) ; ++p ; break ; } } } if(col[ans[p-2]]==col[ans[p-1]]) swap(ans[p-1],ans[0]) ; } for(int i = 1 ; i <= n ; ++i) { if(deg[i]==1) { if(!vi[i]) { ans.push_back(i) ; ++p ; } } } if(p%2) { ans.push_back(ans[p-2]) ; ++p ; } printf("%d\n",p/2) ; for(int i = 0 ; i < p ; i += 2) { printf("%d %d\n",ans[i],ans[i+1]) ; } return 0 ; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 12032 KB | Output is correct |
2 | Correct | 9 ms | 12032 KB | Output is correct |
3 | Correct | 10 ms | 12032 KB | Output is correct |
4 | Correct | 9 ms | 12032 KB | Output is correct |
5 | Correct | 9 ms | 12032 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 | 10 ms | 12032 KB | Output is correct |
10 | Incorrect | 9 ms | 12032 KB | Breaking single line is causing network to disconnect. |
11 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 12032 KB | Output is correct |
2 | Correct | 9 ms | 12032 KB | Output is correct |
3 | Correct | 10 ms | 12032 KB | Output is correct |
4 | Correct | 9 ms | 12032 KB | Output is correct |
5 | Correct | 9 ms | 12032 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 | 10 ms | 12032 KB | Output is correct |
10 | Incorrect | 9 ms | 12032 KB | Breaking single line is causing network to disconnect. |
11 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 12032 KB | Output is correct |
2 | Correct | 9 ms | 12032 KB | Output is correct |
3 | Correct | 10 ms | 12032 KB | Output is correct |
4 | Correct | 9 ms | 12032 KB | Output is correct |
5 | Correct | 9 ms | 12032 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 | 10 ms | 12032 KB | Output is correct |
10 | Incorrect | 9 ms | 12032 KB | Breaking single line is causing network to disconnect. |
11 | Halted | 0 ms | 0 KB | - |