Submission #284005

#	Time	Username	Problem	Language	Result	Execution time	Memory
284005		aloo123	Network (BOI15_net)	C++14	0 / 100	7 ms	12032 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;
	for(int i =2;i<=n;i++){
		int u,v;
		cin >> u >> v;adj[u].pb(v);adj[v].pb(u);
	}

	dfs(1,-1);
	reverse(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,j=leaf.size()-1;i<j;i++,j--){
			cout << leaf[i] << " " << leaf[j] << endl;
		}
		vector<bool> vis(n+1,false);
		for(auto v:adj[leaf[leaf.size()/2]]){
			vis[v] = true;
		}
		int node = -1,maxdeg = 0;
		for(int i =1;i<=n;i++){
			if(!vis[i] && adj[i].size() > maxdeg){
				maxdeg = adj[i].size();
				node = i;
			}
		}
		cout << node << " " << leaf[leaf.size()/2] << endl;
	}
	else{
		cout << ((leaf.size() + 1) >> 1) << endl;
		for(int i = 0,j=leaf.size()-1;i<j;i++,j--){
			cout << leaf[i] << " " << leaf[j] << endl;
		}
	}

	return 0;
}


//Hello, this is a snippet.

Compilation message (stderr)

net.cpp: In function 'int main()':
net.cpp:90:32: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   90 |    if(!vis[i] && adj[i].size() > maxdeg){
      |                  ~~~~~~~~~~~~~~^~~~~~~~

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