Submission #305446

#TimeUsernameProblemLanguageResultExecution timeMemory
305446shahriarkhanNetwork (BOI15_net)C++14
0 / 100
12 ms12032 KiB
#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 , 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 (stderr)

net.cpp: In function 'int main()':
net.cpp:23:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   23 |     scanf("%d",&n) ;
      |     ~~~~~^~~~~~~~~
net.cpp:28:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   28 |         scanf("%d%d",&u,&v) ;
      |         ~~~~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...