Submission #280159

#	Time	Username	Problem	Language	Result	Execution time	Memory
280159		test2	Network (BOI15_net)	C++14	100 / 100	561 ms	83056 KiB

net

#include<bits/stdc++.h>

#define I inline void 

using namespace std ; 

using ll = long long ; 
using ld = long double ; 

const int N = 2e6 + 7 ; 

// How interesting!

int n; 
vector<int> adj[N] ; 
vector<pair<int , int> > ans ; 

vector<int> leafs ; 

I dfs(int x, int p){
	for(auto u : adj[x]){
		if(u == p)
			continue ; 
		dfs(u , x) ; 
	}
	if(adj[x].size() == 1)
		leafs.push_back(x) ; 
}


int main(){
	ios_base::sync_with_stdio(0) ; 
	cin.tie(0) ; 
	//freopen("in.in", "r" , stdin) ;

	cin >> n ; 
	for(int i = 0 ;i < n -1 ;i ++){
		int u , v; 
		cin >> u >> v ; 
		adj[u].push_back(v) ; 
		adj[v].push_back(u) ; 
	}

	dfs(1 , 1) ; 

	if(leafs.size() & 1){
		cout<< (int) leafs.size() / 2 + 1<<"\n" ; 
		for(int i = 0 ;i < leafs.size() / 2 ; i++){
			cout<< leafs[i] <<" " << leafs[i + leafs.size() / 2 + 1] <<"\n" ; 
		}
		cout<< leafs[leafs.size() / 2] <<" " << 1 <<"\n" ; 
	}
	else{
		cout<< (int) leafs.size() / 2 <<"\n" ; 
		for(int i = 0 ;i <(int) leafs.size() / 2 ; i++){
			cout<< leafs[i] <<" " << leafs[i + leafs.size() / 2] <<"\n" ; 
		}
	}
	return 0 ; 
}

Compilation message (stderr)

net.cpp: In function 'int main()':
net.cpp:48:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |   for(int i = 0 ;i < leafs.size() / 2 ; i++){
      |                  ~~^~~~~~~~~~~~~~~~~~

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