Submission #793650

#	Time	Username	Problem	Language	Result	Execution time	Memory
793650		rk42745417	Network (BOI15_net)	C++17	100 / 100	379 ms	58692 KiB

net

#include <bits/stdc++.h>
using namespace std;
 
#define EMiliaMyWife ios::sync_with_stdio(0); cin.tie(0);
using ll = int64_t;
using ull = uint64_t;
using uint = uint32_t;
using ld = long double;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const ll LINF = ll(2e18) + ll(1e15);
const double EPS = 1e-8;
static auto LamyIsCute = []() {
	EMiliaMyWife
	return 48763;
}();
 
signed main() {
	int n;
	cin >> n;
	vector<vector<int>> edge(n + 1);
	for(int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		edge[u].push_back(v);
		edge[v].push_back(u);
	}
	vector<int> tim(n + 1);
	int t = 1;
	function<void(int, int)> dfs = [&](int u, int p) {
		tim[u] = t++;
		for(int v : edge[u])
			if(v != p)
				dfs(v, u);
	};
	for(int i = 1; i <= n; i++)
		if(!tim[i])
			dfs(i, i);
	vector<pair<int, int>> owo, ans;
	for(int i = 1; i <= n; i++)
		if(edge[i].size() == 1)
			owo.push_back({tim[i], i});
	sort(owo.begin(), owo.end());
	for(int i = 0; i < owo.size() / 2; i++)
		ans.push_back({owo[i].second, owo[i + owo.size() / 2].second});
	if(owo.size() & 1)
		ans.push_back({owo[owo.size() / 2].second, owo.back().second});
 
	cout << ans.size() << '\n';
	for(const auto &[a, b] : ans)
		cout << a << ' ' << b << '\n';
}

Compilation message (stderr)

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

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