Submission #1035486

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035486		pacman	Network (BOI15_net)	C++14	0 / 100	6 ms	12376 KiB

net

/******************************************************
| '_ \ / _` |/ __| '_ ` _ \ / _` | '_ \
| |_) | (_| | (__| | | | | | (_| | | | |
| .__/ \__,_|\___|_| |_| |_|\__,_|_| |_|
|_|

__|      |____________________________________________
     ,--.    ,--.          ,--.   ,--.
    |oo  | _  \  `.       | oo | |  oo|
o  o|~~  |(_) /   ;       | ~~ | |  ~~|o  o  o  o  o
    |/\/\|   '._,'        |/\/\| |/\/\|
__________________        ____________________________
******************************************************/

#include <bits/stdc++.h>
//#include "bigint.h"
#define db(x) cerr << #x << ": " << x << endl
#define print cerr << "Ah shit, here we go agian" << endl
#define ll long long int
#define vii vector<int>
#define pii pair<int ,int>
#define vpi vector< pii >
#define ff first
#define ss second
#define mp make_pair
#define mod 1000000007

using namespace std;

const int maxn = 5e5 + 100;

int n, root, par[maxn];

vii adj[maxn];
vii barg;

void dfs(int v ,int mpar){
	par[v] = mpar;
	bool c = false;
	for(auto u : adj[v]){
		if(u != mpar){
			c = true;
			dfs(u ,v);
		}
	}
	if(!c){
		barg.push_back(v);
	}
}


void solve(){
	cin >> n;
	
	for(int i = 0 ; i < n - 1; i++){
		int x ,y;
		cin >> x >> y;
		adj[x].push_back(y);
		adj[y].push_back(x);
		if(adj[x].size() > 1){
			root = x;
		}
		if(adj[y].size() > 1){
			root = y;
		}
	}
	
	dfs(root, -1);
	
	cout << (barg.size() + 1) / 2 << endl;
	
	if(barg.size() % 2 == 0){
		for(int i = 1 ; i < barg.size(); i += 2){
			cout << barg[i - 1] << ' ' << barg[i] << endl;
		}
	}
	else{
		for(int i = 1 ; i < barg.size() - 1; i += 2){
			cout << barg[i] << ' ' << barg[i - 1] << endl;
		}
		cout << barg[barg.size() - 1] << ' ' << adj[par[barg[barg.size() - 1]]][0] << endl;
	}
}


signed main(){

	ios_base::sync_with_stdio(0), cin.tie(0) ,cout.tie(0);

	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);

	int t = 1;
	//cin >> t;
	while(t--){
		solve();
	}

	return 0;
}

Compilation message (stderr)

net.cpp: In function 'void solve()':
net.cpp:73:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |   for(int i = 1 ; i < barg.size(); i += 2){
      |                   ~~^~~~~~~~~~~~~
net.cpp:78:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |   for(int i = 1 ; i < barg.size() - 1; i += 2){
      |                   ~~^~~~~~~~~~~~~~~~~

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