Submission #394620

#	Time	Username	Problem	Language	Result	Execution time	Memory
394620		minoum	Network (BOI15_net)	C++17	100 / 100	612 ms	53440 KiB

net

#include<bits/stdc++.h>

using namespace std;
typedef long long int ll;

const int MAXN = 5e5+10;
int n, st[MAXN], tim = 0, r = -1, lfc = 0, par[MAXN];
vector <int> adj[MAXN], tof;
vector <pair<int,int>> ans;
bool dead[MAXN];

void dfs(int v, int parv){
	st[v] = tim++;
	if((int)adj[v].size()==1) ans.push_back({st[v],v});
	for(int u: adj[v])
		if(u!=parv && !dead[u]) dfs(u,v);
	return;
}

void dfs1(int v, int parv){
	for(int u: adj[v])
		if(u != parv){
			par[u] = v;
			dfs1(u,v);
		}
	return;
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n;
	for(int i = 0; i < n-1; i++){
		int u,v;
		cin >> u >> v; u--; v--;
		adj[v].push_back(u);
		adj[u].push_back(v);
	}
	for(int i = 0; i < n; i++)
		if((int)adj[i].size()==1) tof.push_back(i);
	if(tof.size()==2){
		cout << 1 << '\n' << tof[0]+1 << " " << tof[1]+1 << '\n';
		return 0;
	}
	for(int i = 0; i < n; i++)
		if((int)adj[i].size()>=3) r = i;
	par[r] = -1;
	dfs1(r,-1);
	lfc = ((int)tof.size()+1)/2;
	cout << lfc << '\n';
	if((int)tof.size()%2==1){
		int v = tof.back(), v2 = v; tof.pop_back();
		while((int)adj[v].size()<=2){
			dead[v] = true; v = par[v];
		}
		cout << v2+1 << " " << r+1 << '\n';
	}
	dfs(r,-1);
	sort(ans.begin(), ans.end());
	lfc = (int)ans.size()/2;
	for(int i = 0; i < lfc; i++) cout << ans[i].second+1 << " " << ans[i+lfc].second+1 << '\n';
	return 0; 
}

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