| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 202371 | 2020-02-15T20:20:17 Z | CaroLinda | Park (BOI16_park) | C++14 | 1605 ms | 33504 KB |
#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
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1166 ms | 32120 KB | Output is correct |
| 2 | Correct | 1234 ms | 32200 KB | Output is correct |
| 3 | Correct | 1089 ms | 32248 KB | Output is correct |
| 4 | Correct | 1168 ms | 32248 KB | Output is correct |
| 5 | Correct | 1113 ms | 31992 KB | Output is correct |
| 6 | Correct | 1079 ms | 32112 KB | Output is correct |
| 7 | Correct | 1533 ms | 32120 KB | Output is correct |
| 8 | Correct | 1510 ms | 32120 KB | Output is correct |
| 9 | Correct | 5 ms | 376 KB | Output is correct |
| 10 | Correct | 5 ms | 376 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 78 ms | 2932 KB | Output is correct |
| 2 | Correct | 75 ms | 2912 KB | Output is correct |
| 3 | Correct | 86 ms | 2936 KB | Output is correct |
| 4 | Correct | 79 ms | 2940 KB | Output is correct |
| 5 | Correct | 76 ms | 2936 KB | Output is correct |
| 6 | Correct | 81 ms | 2936 KB | Output is correct |
| 7 | Correct | 60 ms | 1912 KB | Output is correct |
| 8 | Correct | 60 ms | 1912 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1166 ms | 32120 KB | Output is correct |
| 2 | Correct | 1234 ms | 32200 KB | Output is correct |
| 3 | Correct | 1089 ms | 32248 KB | Output is correct |
| 4 | Correct | 1168 ms | 32248 KB | Output is correct |
| 5 | Correct | 1113 ms | 31992 KB | Output is correct |
| 6 | Correct | 1079 ms | 32112 KB | Output is correct |
| 7 | Correct | 1533 ms | 32120 KB | Output is correct |
| 8 | Correct | 1510 ms | 32120 KB | Output is correct |
| 9 | Correct | 5 ms | 376 KB | Output is correct |
| 10 | Correct | 5 ms | 376 KB | Output is correct |
| 11 | Correct | 78 ms | 2932 KB | Output is correct |
| 12 | Correct | 75 ms | 2912 KB | Output is correct |
| 13 | Correct | 86 ms | 2936 KB | Output is correct |
| 14 | Correct | 79 ms | 2940 KB | Output is correct |
| 15 | Correct | 76 ms | 2936 KB | Output is correct |
| 16 | Correct | 81 ms | 2936 KB | Output is correct |
| 17 | Correct | 60 ms | 1912 KB | Output is correct |
| 18 | Correct | 60 ms | 1912 KB | Output is correct |
| 19 | Correct | 1195 ms | 33476 KB | Output is correct |
| 20 | Correct | 1236 ms | 33492 KB | Output is correct |
| 21 | Correct | 1184 ms | 33504 KB | Output is correct |
| 22 | Correct | 1090 ms | 33400 KB | Output is correct |
| 23 | Correct | 1159 ms | 33400 KB | Output is correct |
| 24 | Correct | 1605 ms | 33400 KB | Output is correct |