Submission #821787

#TimeUsernameProblemLanguageResultExecution timeMemory
821787exodus_Network (BOI15_net)C++14
0 / 100
7 ms12116 KiB
#include<bits/stdc++.h> #define fi first #define se second using namespace std; const int nmax = 500005; vector<int>adj[nmax]; bool leaf[nmax]={0}; bool vis[nmax]={0}; vector<pair<int,int>>dist; vector<pair<int,int>>daft; void dfs(int x) { stack<pair<int,int>>st; st.push({x,1}); while(!st.empty()) { int nod = st.top().fi; int dis = st.top().se; vis[nod]=true; if(leaf[nod]) { dist.push_back({dis,nod}); } st.pop(); for(auto it:adj[nod]) { if(vis[it]==false) { st.push({it, dis+1}); } } } return; } int main() { int n,a,b; cin >> n; for(int i=1; i<n; i++) { cin >> a >> b; adj[a].push_back(b); adj[b].push_back(a); } int randomleaf; for(int i=1; i<=n; i++) { if(adj[i].size()==1) { leaf[i]=true; randomleaf=i; } } dfs(randomleaf); sort(dist.begin(), dist.end()); int mid = dist.size()/2; if(dist.size()%2==1) { int j=mid+1; for(int i=0; i<dist.size()/2; i++) { daft.push_back({dist[i].se, dist[j].se}); j++; } daft.push_back({dist[mid].se,dist[0].se}); } else { int j = mid; for(int i=0; i<dist.size()/2; i++) { daft.push_back({dist[i].se, dist[j].se}); j++; } } cout << daft.size() << endl; for(int i=0; i<daft.size(); i++) { cout << daft[i].fi << " " << daft[i].se << endl; } return 0; }

Compilation message (stderr)

net.cpp: In function 'int main()':
net.cpp:50:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         for(int i=0; i<dist.size()/2; i++) {
      |                      ~^~~~~~~~~~~~~~
net.cpp:57:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         for(int i=0; i<dist.size()/2; i++) {
      |                      ~^~~~~~~~~~~~~~
net.cpp:63:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for(int i=0; i<daft.size(); i++) {
      |                  ~^~~~~~~~~~~~
net.cpp:45:8: warning: 'randomleaf' may be used uninitialized in this function [-Wmaybe-uninitialized]
   45 |     dfs(randomleaf);
      |     ~~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...