Submission #1225192

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225192		akqxolotl	Network (BOI15_net)	C++20	100 / 100	371 ms	50104 KiB

net

//Segment Tree is a State of Mind
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr<<#x<<" is "<<x<<endl;
#define debugl(x) cerr << #x << " is "; for(auto p : x) cerr << p << " "; cerr << endl;
#define debugpl(x) cerr<<#x<<" is ";for(auto p:x)cerr<<p.first<<" "<<p.second<<endl;cerr<<endl;

#define int long long
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef pair<int,pii> ipii;
#define pb push_back
#define fi first
#define se second
#define sz(x) (int)(x).size()

int inf=4e18+5;
int mod=1e9+7;

vi adj[500005];
int pre[500005];
int c=0;
vi l;

bool cmp(int a,int b){
	return pre[b]>pre[a];
}

void dfs(int x,int p){
	c++;
	pre[x]=c;
	bool isl=1;
	for(auto i:adj[x]){
		if(i==p)continue;
		isl=0;
		dfs(i,x);
	}
	if(isl)l.pb(x);
}

signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	//mt19937_64 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
	int n;cin>>n;
	for(int i=0;i<n-1;i++){
		int x,y;cin>>x>>y;
		adj[x].pb(y);
		adj[y].pb(x);
	}
	if(sz(adj[1])==1)dfs(adj[1][0],0);
	else dfs(1,0);
	sort(l.begin(),l.end(),cmp);
	int d=sz(l)/2;
	cout<<(sz(l)+1)/2<<'\n';
	for(int i=0;i<d;i++){
		cout<<l[i]<<' '<<l[i+d]<<'\n';
	}
	if(sz(l)%2)cout<<l.back()<<' '<<l[0]<<'\n';
}

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