Submission #497284

#	Time	Username	Problem	Language	Result	Execution time	Memory
497284		aryan12	Network (BOI15_net)	C++17	100 / 100	454 ms	48628 KiB

net

#include <bits/stdc++.h>
using namespace std;
#define int long long

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

const int N = 5e5 + 5;
vector<int> g[N];
vector<int> leaves;

void dfs(int node, int par) {
	if(g[node].size() == 1) {
		leaves.push_back(node);
	}
	for(int i = 0; i < g[node].size(); i++) {
		if(g[node][i] == par) {
			continue;
		}
		dfs(g[node][i], node);
	}
}

void Solve() {
	int n;
	cin >> n;
	for(int i = 1; i < n; i++) {
		int a, b;
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	dfs(1, -1);
	int x = leaves.size();
	cout << (x + 1) / 2 << "\n";
	leaves.push_back(1);
	x++;
	for(int i = 0; i < x / 2; i++) {
		cout << leaves[i] << " " << leaves[i + x / 2] << "\n";
	}
}

int32_t main() {
	auto begin = std::chrono::high_resolution_clock::now();
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--) {
		Solve();
	}
	auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
	return 0;
}

Compilation message (stderr)

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

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