Submission #1127035

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127035		Agageldi	Network (BOI15_net)	C++20	0 / 100	11 ms	14408 KiB

net

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define N 600005
#define ff first
#define ss second
#define pb push_back
#define sz(s) (int)s.size()
#define rep(c, a, b) for(c = a; c <= b; c++)
 
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
ll n, t, out[N], mx, nd;
vector <int> v[N], answer;
vector <pair<int,int>> ans;
map <int,int> vis, vip;

void solve(int x,int answer, int cnt) {
	vis[x] = 1;
	for(auto i:v[x]) {
		if(vis[i]) continue;
		solve(i,answer,cnt + 1);
	}
	if(sz(v[x]) == 1 && vip[x] == 0 && cnt > mx) {
		mx = cnt;
		nd = x;
	}
}
int main () {
	ios::sync_with_stdio(0);cin.tie(0);
	cin >> n;
	for(int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		v[x].pb(y);
		v[y].pb(x);
	}
	for(int i = 1;i<=n;i++) {
		if(sz(v[i]) == 1) answer.pb(i);
	}
	cout << (sz(answer) + 1) / 2 << '\n';
	if(sz(answer) % 2 != 0) {
		t = answer[sz(answer)- 1];
		answer.pop_back();
	}
	for(auto i : answer) {
		if(vip[i]) continue;
		vis.clear();
		mx = nd = 0;
		solve(i, i, 0);
		vip[i] = 1;
		vip[nd] = 1;
		cout << i << " " << nd << '\n';
	}
	if(!t) return 0;
	vip.clear();
	solve(t,t,0);
	cout << t << " " << nd << '\n';
}

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