Submission #655970

#	Time	Username	Problem	Language	Result	Execution time	Memory
655970		Shahrad	Network (BOI15_net)	C++17	100 / 100	439 ms	58696 KiB

net

#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef long double ld;
#define endl '\n'
#define pb push_back
#define mk make_pair
#define sz size()
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define kill(x) return cout << x << endl, void();
#define int ll
typedef pair <int, int> pii;

#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target ("avx2")

const int N = 1e6 + 5;
const int MOD = 998244353, INF = 2e9, MOD2 = 1e9 + 7, sq = 350;

int st[N];
int t;
vector <int> adj[N];
vector <pii> vct;

void dfs (int v, int par)
{
	st[v] = t++;
	for (int u : adj[v])
		if (u != par)
			dfs (u, v);
}

void Solve ()
{
	int n, v, u;
	cin >> n;
	for (int i = 1; i < n; i++)
	{
		cin >> v >> u;
		v--, u--;
		adj[v].pb (u);
		adj[u].pb (v);
	}
	for (int i = 0; i < n; i++)
		if (adj[i].sz > 1)
			v = i;
	dfs (v, -1);
	for (int i = 0; i < n; i++)
		if (adj[i].sz == 1)
			vct.pb (mk (st[i], i));
	sort (all (vct));
	cout << (vct.sz + 1) / 2 << endl;
	if (vct.sz % 2)
		cout << vct.back ().S + 1 << ' ' << vct[0].S + 1 << endl;
	for (int i = 0; i < vct.sz / 2; i++)
		cout << vct[i].S + 1 << ' ' << vct[i + vct.sz / 2].S + 1 << endl;
}

int32_t main ()
{
	ios::sync_with_stdio (0), cin.tie (0), cout.tie (0);
	int tt = 1;
//	cin >> tt;
	while (tt--)
		Solve ();
}

Compilation message (stderr)

net.cpp: In function 'void Solve()':
net.cpp:59:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |  for (int i = 0; i < vct.sz / 2; i++)
      |                  ~~^~~~~~~~~~~~

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