Submission #1270657

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270657		_asunaa	Network (BOI15_net)	C++20	100 / 100	343 ms	58812 KiB

net

#include <bits/stdc++.h>
using namespace std;
long long i, j, l, r, mid, p, q, k, t, n, m, a, b, c, d, ans, cnt, res, arr[500005], arr2[500005], arr3[500005];
const long long mod = 999993143, mod2 = 999993469;
string s;
bool check;
vector <long long> arr4[500005];
vector <pair <long long, long long> > leaves, aa;

void dfs (long long v){
	if (arr2[v] != -1){
		return;
	}
	p += 1;
	arr2[v] = 1;
	arr3[v] = p;
//	cout << v << " " << p << " a\n";
	if (arr4[v].size() == 1 && v != 1){
		return;
	}
	long long i;
	for (i = 0; i < arr4[v].size(); i += 1){
		if (arr2[arr4[v][i]] == -1){
//			cout << arr4[v][i] << " ";
			dfs(arr4[v][i]);
		}
	}
//	cout << "\n";
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for (i = 1; i < n; i += 1){
		cin >> a >> b;
		arr4[a].push_back(b);
		arr4[b].push_back(a);
	}
	for (i = 1; i <= n; i += 1){
		arr2[i] = -1;
	}
	p = 0;
	dfs(1);
	for (i = 1; i <= n; i += 1){
		if (arr4[i].size() == 1){
			leaves.push_back(make_pair(arr3[i], i));
//			cout << arr3[i] << " " << i << "\n";
		}
	}
	d = (leaves.size() + 1) / 2;
	sort(leaves.begin(), leaves.end());
	for (i = 0; i < d; i += 1){
		if (leaves[i].second != leaves[(i + d) % leaves.size()].second){
			aa.push_back(make_pair(leaves[i % leaves.size()].second, leaves[(i + d) % leaves.size()].second));
		}
	}
	cout << aa.size() << "\n";
	for (i = 0; i < aa.size(); i += 1){
		cout << aa[i].first << " " << aa[i].second << "\n";
	}
}

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