Submission #118579

#	Time	Username	Problem	Language	Result	Execution time	Memory
118579		dolphingarlic	Network (BOI15_net)	C++14	100 / 100	926 ms	47860 KiB

net

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

vector<int> graph[500001], leaves;

void dfs(int node = 1, int parent = 0) {
	// cout << node << ' ' << parent << '\n';
	if (graph[node].size() == 1) leaves.push_back(node);
	for (int i : graph[node]) {
		if (i == parent) continue;
		dfs(i, node);
	}
}

int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		int a, b;
		cin >> a >> b;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
	// for (int i : graph[4]) cout << i << ' ';
	// cout << '\n';
	dfs();
	// for (int i : leaves) cout << i << ' ';
	// cout << '\n';
	cout << (leaves.size() + 1) / 2 << '\n';
	for (int i = 0; i < (leaves.size() + 1) / 2; i++) cout << leaves[i] << ' ' << leaves[i + leaves.size() / 2] << '\n';
	return 0;
}

Compilation message (stderr)

net.cpp: In function 'int main()':
net.cpp:30:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < (leaves.size() + 1) / 2; i++) cout << leaves[i] << ' ' << leaves[i + leaves.size() / 2] << '\n';
                  ~~^~~~~~~~~~~~~~~~~~~~~~~~~

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