Submission #107936

#	Time	Username	Problem	Language	Result	Execution time	Memory
107936		shash42	Network (BOI15_net)	C++11	100 / 100	971 ms	73160 KiB

net

#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define pii pair<int, int>

using namespace std;

const int N=5e5+5;
int n, tmr=0;
vector<int> adj[N], lvlst[N];
vector< pii > ans;
int lv[N], p[N];

struct lvsrt
{
	bool operator()(const int &a, const int &b)
	{
		return lv[a]>lv[b];
	}	
};
void dfs(int u)
{
	for(auto &v: adj[u])
	{
		if(v!=p[u])
		{
			p[v]=u;
			dfs(v);
			lv[u]+=lv[v];
		}
	}
	if(adj[u].size()==1 && u!=1)
	{
		tmr++;
		lv[u]=1;
	}
}
int findg(int u)
{
	//cout << tmr << " finding g: " << u << endl;
	for(auto &v: adj[u])
	{
		if(lv[v]>tmr/2 && p[u]!=v)
		{
			return findg(v);
		}
	}
	return u;
}
void findlvs(int u, int subt)
{
	for(auto &v: adj[u])
	{
		if(v!=p[u])
		{
			p[v]=u;
			findlvs(v, subt);
		}
	}
	if(adj[u].size()==1)
	{
		lvlst[subt].pb(u);
	}
}
int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n;
	for(int i = 1; i < n; i++)
	{
		int u, v;
		cin >> u >> v;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	p[1]=1;	
	dfs(1);
	if(adj[1].size()==1) tmr++;
	int g=findg(1);
//	cout << g;
	sort(adj[g].begin(), adj[g].end(), lvsrt());
	memset(p, 0, n+1);
	int numsubt=adj[g].size();
	for(int i = 0; i < numsubt; i++)
	{
		p[adj[g][i]]=g;
		findlvs(adj[g][i], i);
	}
	int itr=0;
	for(int i = 0; i < tmr/2; i++) ans.pb(mp(0, 0));
	bool chk=false;
	for(int i = 0; i < numsubt; i++)
	{
		for(auto &v: lvlst[i])
		{
			if(!chk && itr==tmr/2)
			{
				itr=0;
				chk=true;
			}
			if(!chk) ans[itr].first=v;
			else ans[itr].second=v;
			if(chk && itr==tmr/2) break;
			itr++;
		}
	}
	if(tmr%2)
	{
		ans.pb(mp(g, lvlst[numsubt-1].back()));
	}
	cout << ans.size() << "\n";
	for(auto &v: ans)
	{
		cout << v.first << " " << v.second << "\n";
	}
}

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