Submission #166592

#	Time	Username	Problem	Language	Result	Execution time	Memory
166592		Lawliet	Network (BOI15_net)	C++17	100 / 100	879 ms	94788 KiB

net

#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> pii;

const int MAXN = 500010;

int n;

int sub[MAXN];

vector< int > adj[MAXN];
vector< int > group[MAXN];

set< pii > s;

void DFS(int cur, int p, int t)
{
	if( adj[cur].size() == 1 )
	{
		sub[ cur ] = 1;

		group[ t ].push_back( cur );

		return;
	}

	for(int i = 0 ; i < adj[cur].size() ; i++)
	{
		int viz = adj[cur][i];

		if( viz == p ) continue;

		DFS( viz , cur , t );

		sub[ cur ] += sub[ viz ];
	}
}

int findPendantCentroid(int cur, int p, int s)
{
	for(int i = 0 ; i < adj[cur].size() ; i++)
	{
		int viz = adj[cur][i];

		if( viz == p ) continue;

		if( 2*sub[viz] > s ) return findPendantCentroid( viz , cur , s );
	}

	return cur;
}

void add(int i) { s.insert( { -group[i].size() , i } ); }

int main()
{
	scanf("%d",&n);

	for(int i = 1 ; i < n ; i++)
	{
		int U, V;
		scanf("%d %d",&U,&V);

		adj[ U ].push_back( V );
		adj[ V ].push_back( U );
	}

	int root = 0;

	for(int i = 1 ; i <= n ; i++)
		if( adj[i].size() > 1 ) root = i;

	DFS( root , root , 0 );

	int t = 0;
	int qtdLeafs = sub[root];
	int c = findPendantCentroid( root , root , sub[root] );

	for(int i = 0 ; i < adj[c].size() ; i++)
	{
		int viz = adj[c][i];

		DFS( viz , c , ++t );

		add( t );
	}

	int lastLeaf;

	printf("%d\n",( qtdLeafs + 1 )/2);

	while( qtdLeafs > 1 )
	{
		int curU = s.begin()->second; s.erase( s.begin() );
		int curV = s.begin()->second; s.erase( s.begin() );

		printf("%d %d\n",group[curU].back(),group[curV].back());

		lastLeaf = group[curU].back();

		qtdLeafs -= 2;

		group[ curU ].pop_back();
		group[ curV ].pop_back();

		if( !group[ curU ].empty() ) add( curU );
		if( !group[ curV ].empty() ) add( curV );
	}

	if( qtdLeafs == 1 )
	{
		int curU = s.begin()->second; s.erase( s.begin() );

		printf("%d %d\n",lastLeaf,group[curU].back());
	}
}

Compilation message (stderr)

net.cpp: In function 'void DFS(int, int, int)':
net.cpp:28:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < adj[cur].size() ; i++)
                  ~~^~~~~~~~~~~~~~~~~
net.cpp: In function 'int findPendantCentroid(int, int, int)':
net.cpp:42:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < adj[cur].size() ; i++)
                  ~~^~~~~~~~~~~~~~~~~
net.cpp: In function 'int main()':
net.cpp:80:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < adj[c].size() ; i++)
                  ~~^~~~~~~~~~~~~~~
net.cpp:58:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
net.cpp:63:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&U,&V);
   ~~~~~^~~~~~~~~~~~~~~

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