Submission #426351

#	Time	Username	Problem	Language	Result	Execution time	Memory
426351		Benmath	Network (BOI15_net)	C++14	100 / 100	859 ms	49644 KiB

net

#include<bits/stdc++.h>
using namespace std;vector<int>adjl[500001];
int vis[500001];
vector<int>v;
void dfs(int s){
   vis[s]++;
   int bro=0;
   for(int i=0;i<adjl[s].size();i++){
      if(vis[adjl[s][i]]==0){
         bro++;
         
      }
   }
   if(bro==0){
      v.push_back(s);
   }else{
        for(int i=0;i<adjl[s].size();i++){
      if(vis[adjl[s][i]]==0){
        dfs(adjl[s][i]);
         
      }
   }
   }
}
int main(){
   ios_base::sync_with_stdio(false); cin.tie(NULL);

int n;
cin>>n;
for(int i=0;i<(n-1);i++){
   int x,y;
   cin>>x>>y;
   x--;
   y--;
   adjl[x].push_back(y);
   adjl[y].push_back(x);
}
for(int j=0;j<n;j++){
   if(adjl[j].size()!=1){
      dfs(j);
      int x=v.size();
      if(x%2==0){
         cout<<x/2<<endl;
         int y=x/2;
         for(int i=0;i<y;i++){
            cout<<v[i]+1<<" "<<v[i+y]+1<<endl;
         }
      }else{
         cout<<x/2+1<<endl;
         int y=x/2+1;
         for(int i=0;i<(y-1);i++){
            cout<<v[i]+1<<" "<<v[i+y]+1<<endl;
         }
         cout<<v[y-1]+1<<" "<<j+1<<endl;
      }
      break;
   }
}
}

Compilation message (stderr)

net.cpp: In function 'void dfs(int)':
net.cpp:9:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 |    for(int i=0;i<adjl[s].size();i++){
      |                ~^~~~~~~~~~~~~~~
net.cpp:18:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |         for(int i=0;i<adjl[s].size();i++){
      |                     ~^~~~~~~~~~~~~~~

• Subtask 1: 18 / 18
• Subtask 2: 45 / 45
• Subtask 3: 37 / 37