제출 #226420

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
226420		Lawliet	도시들 (IOI15_towns)	C++17	35 / 100	32 ms	1152 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 120;

int n;
int A, B;
int distCenter;

int dist[MAXN][MAXN];

vector< int > center;

int query(int X, int Y)
{
	if( dist[X][Y] == -1 )
		dist[X][Y] = dist[Y][X] = getDistance( X , Y );

	return dist[X][Y];
}

int intersection(int X, int Y, int C)
{
	int ans = query( X , Y ) + query( X , C );
	ans -= query( Y , C );

	return ans/2;
}

bool isEqual(int X, int Y)
{
	int intersectX = intersection( A , 0 , X );
	int intersectY = intersection( A , 0 , Y );

	if( intersectX < distCenter && intersectY < distCenter ) return true;
	if( intersectX > distCenter && intersectY > distCenter ) return true;
	if( intersectX != distCenter || intersectY != distCenter ) return false;

	return intersection( A , X , Y ) != distCenter;
}

bool majorityProblem()
{
	vector< int > v;
	vector< int > posMajority;

	v.push_back( 0 );

	for(int i = 1 ; i < n ; i++)
	{
		if( !isEqual( i , v.back() ) )
		{
			v.push_back( i );

			if( !posMajority.empty() )
			{
				v.push_back( posMajority.back() );
				posMajority.pop_back();
			}
		}
		else posMajority.push_back( i );
	}

	int majoritary = v.back();

	while( !v.empty() )
	{
		if( isEqual( v.back() , majoritary ) ) v.pop_back();
		else
		{
			if( posMajority.empty() ) return true;
			posMajority.pop_back();
		}

		if( v.empty() ) break;

		v.pop_back();
	}

	return posMajority.empty();
}

int getRadius()
{
	for(int i = 0 ; i < n ; i++)
		if( query( 0 , A ) < query( 0 , i ) ) A = i;

	for(int i = 0 ; i < n ; i++)
		if( query( A , B ) < query( A , i ) ) B = i;

	int diameter = query( A , B );
	int radius = diameter;

	for(int i = 0 ; i < n ; i++)
	{
		int curRadius = intersection( A , 0 , i );
		curRadius = max( curRadius , diameter - curRadius );

		if( curRadius <= radius )
		{
			if( curRadius < radius )
				center.clear();

			radius = curRadius;
			center.push_back( i );
		}
	}

	if( center.size() > 1 )
	{
		if( intersection( A , 0 , center[0] ) > intersection( A , 0 , center[1] ) )
			swap( center[0] , center[1] );

		int qtdLeft = 0;
		int qtdRight = 0;
		int division = intersection( A , 0 , center[0] );

		for(int i = 0 ; i < n ; i++)
		{
			int curDist = intersection( A , 0 , i );

			if( curDist > division ) qtdLeft++; 
			if( curDist < division ) qtdRight++;
 		}

		if( qtdLeft > n/2 || qtdRight > n/2 )
			swap( center[0] , center[1] );
	}

	distCenter = intersection( A , 0 , center[0] );

	return radius;
}

int hubDistance(int N, int sub) 
{
	n = N;

	memset( dist , -1 , sizeof(dist) );

	for(int i = 0 ; i < N ; i++)
		dist[i][i] = 0;

	int R = getRadius();
	bool isBalanced = majorityProblem();

	if( isBalanced ) return R;
	return -R;
}

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

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:137:28: warning: unused parameter 'sub' [-Wunused-parameter]
 int hubDistance(int N, int sub) 
                            ^~~

• Subtask 1: 13 / 13
• Subtask 2: 12 / 12
• Subtask 3: 0 / 13
• Subtask 4: 10 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 39