Submission #284020

#	Time	Username	Problem	Language	Result	Execution time	Memory
284020		aloo123	Network (BOI15_net)	C++14	100 / 100	525 ms	56104 KiB

net

    		#include <bits/stdc++.h>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <cstring>
    #include <chrono>
    #include <complex>
    #define endl "\n"
    #define ll long long int
    #define vi vector<int>
    #define vll vector<ll>
    #define vvi vector < vi >
    #define pii pair<int,int>
    #define pll pair<long long, long long>
    #define mod 1000000007
    #define inf 1000000000000000001;
    #define all(c) c.begin(),c.end()
    #define mp(x,y) make_pair(x,y)
    #define mem(a,val) memset(a,val,sizeof(a))
    #define pb push_back
    #define f first
    #define s second
    #define pi 3.141592653589793238
    using namespace std;
    ll gcd( ll a, ll b )
    {
    	if(b==0)
    	{
    		return a;
    	}
    	else
    	{
    		return gcd( b, a%b );
    	}
    }
    ll lcm (ll a, ll b)
    {
    	return (a*b)/gcd(a,b);
    }
     
    ll power(ll a, ll b)	//a is base, b is exponent
    {
    	if(b==0)
    		return 1;
    	if(b==1)
    		return a;
    	if(b%2 == 1)
    		return (power(a,b-1)*a)%mod;
    	ll q = power(a,b/2);
    	return (q*q)%mod;
    }
    vector<int> adj[500005];
    vector<int> leaf;
    void dfs(int u,int p){
    	
    	
    	for(auto v:adj[u]){
    		if(v!=p){
    			dfs(v,u);
    		}
    	}
    	if(adj[u].size() == 1)
    		leaf.pb(u);
    }	
     
    int main()
    {
    	std::ios::sync_with_stdio(false);
    	int n;
    	cin >> n;
    	int nd=-1,maxd=0;
    	for(int i =2;i<=n;i++){
    		int u,v;
    		cin >> u >> v;adj[u].pb(v);adj[v].pb(u);
    		
    	}
    	for(int i =1;i<=n;i++){
    		if(adj[i].size() > maxd){
    			maxd = adj[i].size();
    			nd = i;
    		} 
    	}
    	// cout << nd << endl; 
    	dfs(nd,-1);
    	// sort(leaf.begin(),leaf.end());
    	// for(auto &x:leaf) cout << x << " ";cout<<endl;
    	if(leaf.size() & 1){
    		
    		cout << ((leaf.size() + 1) >> 1) << endl;	
    		for(int i = 0;i<(leaf.size()/2);i++){
    			cout << leaf[i] << " " << leaf[i+(leaf.size()/2)] << endl;
    		}
    		cout << leaf.back() << " " <<nd  << endl;
    	}
    	else{
    		cout << ((leaf.size() + 1) >> 1) << endl;
    		for(int i = 0;i<(leaf.size()/2);i++){
    			cout << leaf[i] << " " << leaf[i+(leaf.size()/2)] << endl;
    		}
    	}
     
    	return 0;
    }
 
//     6
// 1 2
// 2 3
// 2 4
// 4 5
// 4 6

// 8
// 1 2
// 2 3
// 3 4 
// 4 5
// 3 6
// 3 7
// 3 8



     

Compilation message (stderr)

net.cpp: In function 'int main()':
net.cpp:80:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   80 |       if(adj[i].size() > maxd){
      |          ~~~~~~~~~~~~~~^~~~~~
net.cpp:92:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |       for(int i = 0;i<(leaf.size()/2);i++){
      |                     ~^~~~~~~~~~~~~~~~
net.cpp:99:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |       for(int i = 0;i<(leaf.size()/2);i++){
      |                     ~^~~~~~~~~~~~~~~~

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