Submission #1025181

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025181		aykhn	Network (BOI15_net)	C++17	100 / 100	325 ms	105128 KiB

net

#include <bits/stdc++.h>

using namespace std;

#define inf 0x3F3F3F3F

const int MXN = 5e5 + 5, MXK = 21, MXM = 1e7 + 5;
const int LOG = 18;

int n, m = 0, R;
vector<int> adj[MXN];
int sz[MXN];

void getsz(int a, int p)
{
	sz[a] = (adj[a].size() == 1);
	for (int &v : adj[a])
	{
		if (v == p) continue;
		getsz(v, a);
		sz[a] += sz[v];
	}
}

int findcent(int a, int p)
{
	for (int &v : adj[a])
	{
		if (v == p) continue;
		if (sz[v] > m / 2) return findcent(v, a);
	}
	return a;
}

vector<int> x;

void dfs(int a, int p)
{
	if (adj[a].size() == 1) x.push_back(a);
	for (int &v : adj[a])
	{
		if (v == p) continue;
		dfs(v, a);
	}
}

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i = 1; i < n; i++)
	{
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	for (int i = 1; i <= n; i++)
	{
		if (adj[i].size() > 1) R = i;
		m += (adj[i].size() == 1);
	}
	getsz(R, R);
	int c = findcent(R, R);
	vector<vector<int>> V, V1;
	for (int &v : adj[c])
	{
		x.clear();
		dfs(v, c);
		V.push_back(x);
	}
	V1 = V;
	priority_queue<array<int, 2>> pq;
	for (int i = 0; i < V.size(); i++)
	{
		pq.push({(int)V[i].size(), i});
	}
	vector<array<int, 2>> res;
	while (pq.size() > 1)
	{
		array<int, 2> x = pq.top();
		pq.pop();
		array<int, 2> y = pq.top();
		pq.pop();
		res.push_back({V[x[1]].back(), V[y[1]].back()});
		V[x[1]].pop_back();
		V[y[1]].pop_back();
		if (--x[0]) pq.push(x);
		if (--y[0]) pq.push(y);
	}
	if (pq.size() == 1)
	{
		if (pq.top()[1] == 0) 
		{
			res.push_back({V1[0][0], V1[1][0]});
		}
		else
		{
			res.push_back({V1[0][0], V1[pq.top()[1]][0]});
		}
	}
	cout << res.size() << '\n';
	for (array<int, 2> &i : res) cout << i[0] << ' ' << i[1] << '\n';
}

Compilation message (stderr)

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

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