Submission #156701

#	Time	Username	Problem	Language	Result	Execution time	Memory
156701		Lawliet	Race (IOI11_race)	C++14	100 / 100	856 ms	46944 KiB

race

#include <bits/stdc++.h>
 
#define MAX 200010
#define MAXK 1000010
#define INF 1000000010
 
using namespace std;
typedef long long int lli;
typedef pair<int,int> pii;
 
int n, k;
int ans;
 
int sub[MAX];
int minEdge[MAXK];
 
bool isCentroid[MAX];
 
vector< int > peso[MAX];
vector< int > grafo[MAX];
 
vector< pii > updates;
 
void DFSInit(int cur, int p)
{
	sub[ cur ] = 1;
 
	for(int i = 0 ; i < grafo[ cur ].size() ; i++)
	{
		int prox = grafo[ cur ][ i ];
 
		if( prox == p ) continue;
		if( isCentroid[ prox ] ) continue;
 
		DFSInit( prox , cur );
 
		sub[ cur ] += sub[ prox ];
	}
}
 
int findCentroid(int cur, int p, int s)
{
	for(int i = 0 ; i < grafo[ cur ].size() ; i++)
	{
		int prox = grafo[ cur ][ i ];
 
		if( prox == p ) continue;
		if( isCentroid[ prox ] ) continue;
 
		if( sub[ prox ] > s/2 ) return findCentroid( prox , cur , s );
	}
 
	return cur;
}
 
void DFSCalculate(int cur, int p, lli distWeighted, int distUnweighted)
{
	if(distWeighted <= k)
	{
		updates.push_back( { distWeighted , distUnweighted } );
		ans = min( ans , minEdge[ k - distWeighted ] + distUnweighted );
	}
 
	for(int i = 0 ; i < grafo[ cur ].size() ; i++)
	{
		int prox = grafo[ cur ][ i ];
		int w = peso[ cur ][ i ];
 
		if( prox == p ) continue;
		if( isCentroid[ prox ] ) continue;
 
		DFSCalculate( prox , cur , distWeighted + w , distUnweighted + 1 );
	}
}
 
void decompose(int cur, int p)
{
	DFSInit( cur , cur );
 
	int curCentroid = findCentroid( cur , cur , sub[ cur ] );
 
	isCentroid[ curCentroid ] = true;
 
	vector< int > ind;
 
	for(int i = 0 ; i < grafo[ curCentroid ].size() ; i++)
	{
		int prox = grafo[ curCentroid ][ i ];
 		int w = peso[ curCentroid ][ i ];

		if( isCentroid[ prox ] ) continue;
 
		DFSCalculate(prox , curCentroid , w , 1);
 
		while( !updates.empty() )
		{
			int wW = updates.back().first;
			int wU = updates.back().second;
			updates.pop_back();
 
			ind.push_back( wW );
 
			minEdge[ wW ] = min( minEdge[ wW ] , wU );
		}
	}
 
	for(int i = 0 ; i < ind.size() ; i++)
		minEdge[ ind[i] ] = INF;
 
	minEdge[ 0 ] = 0;
 
	for(int i = 0 ; i < grafo[ curCentroid ].size() ; i++)
	{
		int prox = grafo[ curCentroid ][ i ];
 
		if( !isCentroid[ prox ] )
			decompose( prox , curCentroid );
	}
}
 
int best_path(int N, int K, int H[][2], int L[]) 
{
	n = N; k = K;
 
	for(int i = 0 ; i <= k ; i++)
		minEdge[ i ] = INF;
 
	minEdge[ 0 ] = 0;
 
	for(int i = 0 ; i < n - 1 ; i++)
	{
		int U = H[ i ][ 0 ];
		int V = H[ i ][ 1 ];
		int W = L[ i ];
 
		peso[ U ].push_back( W );
		peso[ V ].push_back( W );
 
		grafo[ U ].push_back( V );
		grafo[ V ].push_back( U );
	}
 
	ans = INF;
 
	decompose( 0 , 0 );
 
	if(ans == INF) return -1;
	return ans;
}

Compilation message (stderr)

race.cpp: In function 'void DFSInit(int, int)':
race.cpp:28:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < grafo[ cur ].size() ; i++)
                  ~~^~~~~~~~~~~~~~~~~~~~~
race.cpp: In function 'int findCentroid(int, int, int)':
race.cpp:43:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < grafo[ cur ].size() ; i++)
                  ~~^~~~~~~~~~~~~~~~~~~~~
race.cpp: In function 'void DFSCalculate(int, int, lli, int)':
race.cpp:64:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < grafo[ cur ].size() ; i++)
                  ~~^~~~~~~~~~~~~~~~~~~~~
race.cpp: In function 'void decompose(int, int)':
race.cpp:86:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < grafo[ curCentroid ].size() ; i++)
                  ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
race.cpp:107:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < ind.size() ; i++)
                  ~~^~~~~~~~~~~~
race.cpp:112:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < grafo[ curCentroid ].size() ; i++)
                  ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 57 / 57