Submission #107920

#	Time	Username	Problem	Language	Result	Execution time	Memory
107920		shash42	Network (BOI15_net)	C++11	18 / 100	2037 ms	24056 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()
{
	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;
	for(int i = 0; i < numsubt; i++)
	{
		itr=i+1;
		while(lvlst[i].size())
		{
			if(ans.size()==tmr/2) break;
 			while(!lvlst[itr].size())
			{		
				itr++;
				if(itr==numsubt) itr=i+1;
			}
			if(itr>=numsubt) break;
			ans.pb(mp(lvlst[i].back(), lvlst[itr].back()));
			lvlst[i].pop_back(); lvlst[itr].pop_back();
			itr++;
			if(itr==numsubt) itr=i+1;
		}
	}
	if(tmr%2)
	{
		for(int i = 0; i < numsubt; i++)
		{
			if(lvlst[i].size()) ans.pb(mp(lvlst[i][0], g));
		}
	}
	cout << ans.size() << "\n";
	for(auto &v: ans)
	{
		cout << v.first << " " << v.second << "\n";
	}
}

Compilation message (stderr)

net.cpp: In function 'int main()':
net.cpp:94:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(ans.size()==tmr/2) break;
       ~~~~~~~~~~^~~~~~~

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