Submission #655922

#	Time	Username	Problem	Language	Result	Execution time	Memory
655922		Farbod	Network (BOI15_net)	C++17	100 / 100	438 ms	47516 KiB

net

/*
*  In the name of God
*
*  Author: Farbod Doost
*  Last Modified: Sun, 06 Nov 2022 (09:07:00)
*
*/
#include <iostream>
#include <vector>
using namespace std;

const int N = 5e5 + 1;

int n;
vector <int> adj[N], vec;

void dfs(int v, int p)
{
	for (auto u: adj[v])
		if (u != p)
			dfs(u, v);

	if (adj[v].size() == 1)
		vec.push_back(v);

	return;
}

signed main()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> n;
	for (int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v, u--, v--;

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

	int tmp = ((int)vec.size() + 1) / 2;

	cout << tmp << '\n';
	for (int i = 0; i < tmp - (vec.size() % 2); i++)
		cout << vec[i] + 1 << ' ' << vec[i + tmp] + 1 << '\n';

	if ((int)vec.size() % 2 == 1)
		cout << vec[tmp - 1] + 1 << ' ' << idx + 1 << '\n';

    return 0;
}

Compilation message (stderr)

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

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