제출 #156700

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
156700		Lawliet	경주 (Race) (IOI11_race)	C++14	0 / 100	10 ms	9720 KiB

race

#include <bits/stdc++.h>

#define MAX 200010
#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[MAX];

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 ];

		if( isCentroid[ prox ] ) continue;

		DFSCalculate(curCentroid , curCentroid , 0 , 0);

		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;
}

컴파일 시 표준 에러 (stderr) 메시지

race.cpp: In function 'void DFSInit(int, int)':
race.cpp:27: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:42: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:63: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:85:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < grafo[ curCentroid ].size() ; i++)
                  ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
race.cpp:105:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < ind.size() ; i++)
                  ~~^~~~~~~~~~~~
race.cpp:110:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < grafo[ curCentroid ].size() ; i++)
                  ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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