Submission #656190

#	Time	Username	Problem	Language	Result	Execution time	Memory
656190		Dorost	Network (BOI15_net)	C++17	100 / 100	425 ms	60976 KiB

net

/* 	* In the name of GOD  */

#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
#define F first
#define S second
#define mk make_pair
const int N = 501234;
int st[N], ts[N], cnt = 0;
vector <int> g[N], k;

void dfs(int v, int p) {
	st[v] = cnt;
	ts[cnt] = v;
	cnt++;
	if (g[v].size() == 1)
		k.push_back(st[v]);
	for (auto u : g[v]) {
		if (u != p) {
			dfs(u, v);
		}
	}
}

int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie();
	cout.tie();
	int n;
	cin >> n;
	int root;
	for (int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
		if (g[u].size() >= 2)
			root = u;
		if (g[v].size() >= 2)
			root = v;
	}
	dfs(root, -1);
	cout << ((int)k.size() + 1) / 2 << '\n';
	sort(k.begin(), k.end());
	for (int i = 0; i < ((int)k.size() + 1) / 2; i++)
		cout << ts[k[i]] << ' ' << ts[k[i + ((int)k.size()) / 2]] << '\n';
}

Compilation message (stderr)

net.cpp: In function 'int32_t main()':
net.cpp:46:5: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   46 |  dfs(root, -1);
      |  ~~~^~~~~~~~~~

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