oj.uz

Submission #226420

# Submission time Handle Problem Language Result Execution time Memory
226420 2020-04-23T18:51:08 Z Lawliet Towns (IOI15_towns) C++17
35 / 100
 32 ms 1152 KB 
#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;
}

Compilation message

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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1024 KB Output is correct
2 Correct 22 ms 896 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 31 ms 1016 KB Output is correct
5 Correct 26 ms 1024 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1024 KB Output is correct
2 Correct 21 ms 948 KB Output is correct
3 Correct 32 ms 1024 KB Output is correct
4 Correct 31 ms 1016 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1152 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 896 KB Output isn't correct
2 Halted 0 ms 0 KB -