Submission #202371

#	Time	Username	Problem	Language	Result	Execution time	Memory
202371		CaroLinda	Park (BOI16_park)	C++14	100 / 100	1605 ms	33504 KiB

park

#include <bits/stdc++.h>

#define debug 
#define ll long long
#define quad(x) x*x

const int MAXN = 2010 ;
const ll inf = 3e18 + 10 ;

using namespace std ;

struct Circle
{

	int x , y , rad ;

	Circle(int x=0, int y=0, int rad=0) : x(x) , y(y) , rad(rad) {}

} ;

ll dist( Circle c1, Circle c2 )
{

	ll dx = c1.x - c2.x ;
	ll dy = c1.y - c2.y;

	return dx*dx + dy*dy ;

}

ll find_max_radio(Circle c1, Circle c2)
{


	ll d = dist( c1, c2 ) - quad(1LL*c1.rad) - quad(1LL*c2.rad) - 2LL*c1.rad*c2.rad ;

	ll l = 0 , r = 10000000000 , mid , best = 0 ;

	while( l <= r )
	{
		mid = (l+r)>>1 ;

		long double rad = 1.0*mid*4*( 1.0*mid + 1.0*c1.rad + 1.0*c2.rad ) ;

		if( rad > 2*inf ) 
		{
			r = mid - 1 ;
			continue ;
		}

		ll _rad = mid*4*(mid+c1.rad+c2.rad) ;

		if( _rad > d ) r = mid - 1 ;
		else if( _rad <= d )
		{
			best = mid ;
			l = mid + 1 ;
		}

	}

	return best ;

}

int N , M , W , H ;
int pos[5][5] ;
Circle trees[MAXN] ;
ll mat[MAXN][MAXN] ;
bool reach[MAXN] ;

void dfs(int curr, int weight)
{

	reach[curr] = true ;

	for(int i = 1 ; i <= N+4 ; i++ )
	{
		if( mat[curr][i] >= weight || reach[i] || (curr > N && i > N) ) continue ;

		dfs(i, weight ) ;

	}

}

int main()
{

	scanf("%d%d%d%d", &N , &M , &W, &H) ;
	for(int i = 1 ; i <= N ; i++ )
		scanf("%d%d%d", &trees[i].x, &trees[i].y, &trees[i].rad ) ;

	for(int i = 1 ; i <= N ; i++ )
		for(int j = i+1 ; j <= N ; j++ )
			mat[i][j]= mat[j][i] = find_max_radio(trees[i] , trees[j] ) ;

	for(int i = 1 ; i <= N ; i++ )
	{
		int x = trees[i].x , y = trees[i].y , r = trees[i].rad ;
		//N+1
		mat[N+1][i] = mat[i][N+1] = (x-r)>>1 ;

		//N+2
		mat[N+2][i] = mat[i][N+2] = (H - y-r)>>1 ;

		//N+3
		mat[N+3][i] = mat[i][N+3] = (W-x-r)>>1 ;

		//N+4
		mat[N+4][i] = mat[i][N+4] = (y-r)>>1 ;
	}

	for(int i = 1 ; i <= 4 ; i++ )
		for(int j = i+1 ; j <= 4 ; j++ )
		{
			if( j == i ) continue ;

			int l = 0 , r = 1000000000 , mid , best = 1000001000 ;

			while( l <= r )
			{

				mid = (l+r)>>1 ;

				memset(reach, false, sizeof reach ) ;
				dfs(N+i, mid ) ;

				if( reach[N+j]  ) 
				{
					r = mid-1 ;
					best = mid ;
				}
				else l = mid + 1 ;

			}

			pos[i][j] = best ;

			debug("(%d,%d) = %d\n", i , j , best  ) ;

		}

	/*for(int i = 1 ; i <= N+4 ; i++ , debug("\n") )
		for(int j = 1 ; j <= N+4 ; j++ ) debug("%lld " , mat[i][j] ) ;
	*/

	while(M--)
	{
		int R , E ;
		scanf("%d%d", &R, &E ) ;

		bool can[5] = { 0 , 1 , 1 , 1 , 1 } ;

		for(int i = 1 ; i <= 4 ; i++ )
			for(int j = i+1 ; j <= 4 ; j++ )
			{

				if( pos[i][j] > R ) continue ;

				if(i == 1)
				{
					if( j == 2 )
					{
						if( E == 4 ) can[1] = can[2] = can[3] = false;
						else can[4] = false ;
					}
					if( j == 3 )
					{
						if( E == 1 || E == 2 ) can[3] = can[4] = false ;
						else can[1] = can[2] = false ;
					}
					if( j == 4 )
					{
						if(E == 1) can[2] = can[3] = can[4] = false ;
						else can[1] = false; 
					}
				}				

				if( i == 2 )
				{
					if( j == 3 )
					{
						if( E == 3 ) can[1] = can[2] = can[4] = false ;
						else can[3] = false ;
					}
					if( j == 4 )
					{
						if(E == 2 || E == 3) can[1] = can[4] = false ;
						else can[2] = can[3] = false ;
					}
				}

				if( i == 3 && j == 4 )
				{
					if( E == 2 ) can[1] =can[3] = can[4] = false ;
					else can[2] = false ;
				}

			}

		can[E] = true ;

		for(int i = 1 ; i <= 4 ; i++ )
			if(can[i]) printf("%d",i) ;
		printf("\n") ;

	}


}

Compilation message (stderr)

park.cpp: In function 'int main()':
park.cpp:140:28: warning: left operand of comma operator has no effect [-Wunused-value]
    debug("(%d,%d) = %d\n", i , j , best  ) ;
                            ^
park.cpp:140:32: warning: right operand of comma operator has no effect [-Wunused-value]
    debug("(%d,%d) = %d\n", i , j , best  ) ;
                                ^
park.cpp:140:36: warning: right operand of comma operator has no effect [-Wunused-value]
    debug("(%d,%d) = %d\n", i , j , best  ) ;
                                    ^~~~
park.cpp:90:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d", &N , &M , &W, &H) ;
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:92:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &trees[i].x, &trees[i].y, &trees[i].rad ) ;
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:151:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &R, &E ) ;
   ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 27 / 27
• Subtask 2: 31 / 31
• Subtask 3: 42 / 42