oj.uz

Submission #258546

# Submission time Handle Problem Language Result Execution time Memory
258546 2020-08-06T06:10:21 Z 송준혁(#5060) Park (BOI16_park) C++17
100 / 100
 2012 ms 23672 KB 
#include <bits/stdc++.h>
#define pb push_back
#define lb lower_bound
#define fi first
#define se second
#define mup(a,x) a=min(a,x)
#define Mup(a,x) a=max(a,x)
#define INF 1234567890
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

int N, Q, W, H;
int P[2020];
bool chk[2020];
LL X[2020], Y[2020], R[2020], A[6];
LL D[2020][2020];

int rt(int u){
	if (P[u] == u) return u;
	return P[u] = rt(P[u]);
}

int main(){
	scanf("%d %d", &N, &Q);
	scanf("%d %d", &W, &H);
	for (int i=1; i<=N; i++) scanf("%lld %lld %lld", &X[i], &Y[i], &R[i]);
	LL lo=0, hi=250'000'000;
	for (int i=1; i<N; i++) for (int j=i+1; j<=N; j++) D[i][j] = (X[i]-X[j])*(X[i]-X[j])+(Y[i]-Y[j])*(Y[i]-Y[j]);
	while (lo<=hi){
		LL m=lo+hi>>1;
		for (int i=1; i<=N; i++) P[i] = i;
		for (int i=1; i<N; i++) for (int j=i+1; j<=N; j++) {
			if (D[i][j]<(m+m+R[i]+R[j])*(m+m+R[i]+R[j])){
				P[rt(i)] = rt(j);
			}
		}
		bool tf=false;
		memset(chk, false, sizeof chk);
		for (int i=1; i<=N; i++) if (X[i]-R[i]-m-m < 0) chk[rt(i)] = true;
		for (int i=1; i<=N; i++) if (Y[i]-R[i]-m-m < 0 && chk[rt(i)]) {tf = true; break;}
		if (tf) A[0]=m, hi=m-1;
		else lo=m+1;
	}

	lo=0, hi=250'000'000;
	while (lo<=hi){
		LL m=lo+hi>>1;
		for (int i=1; i<=N; i++) P[i] = i;
		for (int i=1; i<N; i++) for (int j=i+1; j<=N; j++) {
			if (D[i][j]<(m+m+R[i]+R[j])*(m+m+R[i]+R[j])){
				P[rt(i)] = rt(j);
			}
		}
		bool tf=false;
		memset(chk, false, sizeof chk);
		for (int i=1; i<=N; i++) if (X[i]+R[i]+m+m > W) chk[rt(i)] = true;
		for (int i=1; i<=N; i++) if (Y[i]-R[i]-m-m < 0 && chk[rt(i)]) {tf = true; break;}
		if (tf) A[1]=m, hi=m-1;
		else lo=m+1;
	}

	lo=0, hi=250'000'000;
	while (lo<=hi){
		LL m=lo+hi>>1;
		for (int i=1; i<=N; i++) P[i] = i;
		for (int i=1; i<N; i++) for (int j=i+1; j<=N; j++) {
			if (D[i][j]<(m+m+R[i]+R[j])*(m+m+R[i]+R[j])){
				P[rt(i)] = rt(j);
			}
		}
		bool tf=false;
		memset(chk, false, sizeof chk);
		for (int i=1; i<=N; i++) if (X[i]+R[i]+m+m > W) chk[rt(i)] = true;
		for (int i=1; i<=N; i++) if (Y[i]+R[i]+m+m > H && chk[rt(i)]) {tf = true; break;}
		if (tf) A[2]=m, hi=m-1;
		else lo=m+1;
	}

	lo=0, hi=250'000'000;
	while (lo<=hi){
		LL m=lo+hi>>1;
		for (int i=1; i<=N; i++) P[i] = i;
		for (int i=1; i<N; i++) for (int j=i+1; j<=N; j++) {
			if (D[i][j]<(m+m+R[i]+R[j])*(m+m+R[i]+R[j])){
				P[rt(i)] = rt(j);
			}
		}
		bool tf=false;
		memset(chk, false, sizeof chk);
		for (int i=1; i<=N; i++) if (X[i]-R[i]-m-m < 0) chk[rt(i)] = true;
		for (int i=1; i<=N; i++) if (Y[i]+R[i]+m+m > H && chk[rt(i)]) {tf = true; break;}
		if (tf) A[3]=m, hi=m-1;
		else lo=m+1;
	}

	lo=0, hi=250'000'000;
	while (lo<=hi){
		LL m=lo+hi>>1;
		for (int i=1; i<=N; i++) P[i] = i;
		for (int i=1; i<N; i++) for (int j=i+1; j<=N; j++) {
			if (D[i][j]<(m+m+R[i]+R[j])*(m+m+R[i]+R[j])){
				P[rt(i)] = rt(j);
			}
		}
		bool tf=false;
		memset(chk, false, sizeof chk);
		for (int i=1; i<=N; i++) if (X[i]-R[i]-m-m < 0) chk[rt(i)] = true;
		for (int i=1; i<=N; i++) if (X[i]+R[i]+m+m > W && chk[rt(i)]) {tf = true; break;}
		if (tf) A[4]=m, hi=m-1;
		else lo=m+1;
	}

	lo=0, hi=250'000'000;
	while (lo<=hi){
		LL m=lo+hi>>1;
		for (int i=1; i<=N; i++) P[i] = i;
		for (int i=1; i<N; i++) for (int j=i+1; j<=N; j++) {
			if (D[i][j]<(m+m+R[i]+R[j])*(m+m+R[i]+R[j])){
				P[rt(i)] = rt(j);
			}
		}
		bool tf=false;
		memset(chk, false, sizeof chk);
		for (int i=1; i<=N; i++) if (Y[i]-R[i]-m-m < 0) chk[rt(i)] = true;
		for (int i=1; i<=N; i++) if (Y[i]+R[i]+m+m > H && chk[rt(i)]) {tf = true; break;}
		if (tf) A[5]=m, hi=m-1;
		else lo=m+1;
	}

	while (Q--){
		int x, y;
		scanf("%d %d", &x, &y);
		if (y == 1){
			printf("1");
			if (x < A[0] && x < A[1] && x < A[5]) printf("2");
			if (x < A[0] && x < A[2] && x < A[4] && x < A[5]) printf("3");
			if (x < A[0] && x < A[3] && x < A[4]) printf("4");
		}
		if (y == 2){
			if (x < A[0] && x < A[1] && x < A[5]) printf("1");
			printf("2");
			if (x < A[1] && x < A[2] && x < A[4]) printf("3");
			if (x < A[1] && x < A[3] && x < A[4] && x < A[5]) printf("4");
		}
		if (y == 3){
			if (x < A[2] && x < A[0] && x < A[5] && x < A[4]) printf("1");
			if (x < A[1] && x < A[2] && x < A[4]) printf("2");
			printf("3");
			if (x < A[2] && x < A[3] && x < A[5]) printf("4");
		}
		if (y == 4){
			if (x < A[0] && x < A[3] && x < A[4]) printf("1");
			if (x < A[1] && x < A[3] && x < A[4] && x < A[5]) printf("2");
			if (x < A[2] && x < A[3] && x < A[5]) printf("3");
			printf("4");
		}
		printf("\n");
	}
	return 0;
}

Compilation message

park.cpp: In function 'int main()':
park.cpp:31:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   LL m=lo+hi>>1;
        ~~^~~
park.cpp:48:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   LL m=lo+hi>>1;
        ~~^~~
park.cpp:65:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   LL m=lo+hi>>1;
        ~~^~~
park.cpp:82:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   LL m=lo+hi>>1;
        ~~^~~
park.cpp:99:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   LL m=lo+hi>>1;
        ~~^~~
park.cpp:116:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   LL m=lo+hi>>1;
        ~~^~~
park.cpp:25:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &N, &Q);
  ~~~~~^~~~~~~~~~~~~~~~~
park.cpp:26:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &W, &H);
  ~~~~~^~~~~~~~~~~~~~~~~
park.cpp:27:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i=1; i<=N; i++) scanf("%lld %lld %lld", &X[i], &Y[i], &R[i]);
                           ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:133:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 565 ms 23168 KB Output is correct
2 Correct 567 ms 23160 KB Output is correct
3 Correct 572 ms 23168 KB Output is correct
4 Correct 587 ms 23160 KB Output is correct
5 Correct 589 ms 23160 KB Output is correct
6 Correct 580 ms 23072 KB Output is correct
7 Correct 2012 ms 23168 KB Output is correct
8 Correct 1940 ms 23172 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 1784 KB Output is correct
2 Correct 47 ms 1656 KB Output is correct
3 Correct 47 ms 1640 KB Output is correct
4 Correct 44 ms 1656 KB Output is correct
5 Correct 44 ms 1656 KB Output is correct
6 Correct 62 ms 1656 KB Output is correct
7 Correct 43 ms 640 KB Output is correct
8 Correct 37 ms 640 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 565 ms 23168 KB Output is correct
2 Correct 567 ms 23160 KB Output is correct
3 Correct 572 ms 23168 KB Output is correct
4 Correct 587 ms 23160 KB Output is correct
5 Correct 589 ms 23160 KB Output is correct
6 Correct 580 ms 23072 KB Output is correct
7 Correct 2012 ms 23168 KB Output is correct
8 Correct 1940 ms 23172 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 47 ms 1784 KB Output is correct
12 Correct 47 ms 1656 KB Output is correct
13 Correct 47 ms 1640 KB Output is correct
14 Correct 44 ms 1656 KB Output is correct
15 Correct 44 ms 1656 KB Output is correct
16 Correct 62 ms 1656 KB Output is correct
17 Correct 43 ms 640 KB Output is correct
18 Correct 37 ms 640 KB Output is correct
19 Correct 620 ms 23544 KB Output is correct
20 Correct 654 ms 23544 KB Output is correct
21 Correct 613 ms 23672 KB Output is correct
22 Correct 676 ms 23544 KB Output is correct
23 Correct 611 ms 23420 KB Output is correct
24 Correct 1995 ms 23672 KB Output is correct