oj.uz

Submission #647498

# Submission time Handle Problem Language Result Execution time Memory
647498 2022-10-03T01:31:13 Z rsjw Park (BOI16_park) C++17
100 / 100
 694 ms 64676 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
#define double long double
struct point {
	int x,y,r;
} a[2010];
int f[2010];
int N,T,n,m;
double D(point i,point j) {
	return sqrt((double)(i.x-j.x)*(i.x-j.x)+(i.y-j.y)*(i.y-j.y))-i.r-j.r;
}
struct edge {
	int i,j;
	double d;
} b[4004010];
bool cmp(edge a,edge b) {
	return a.d<b.d;
}
int find(int x) {
	if(f[x]==x) return x;
	return f[x]=find(f[x]);
}
void uni(int x,int y) {
	f[find(x)]=find(y);
}
int check(int x,int y) {
	return find(x)==find(y);
}
double r[5][5];
bool ud() {
	return check(N+1,N+2);
}
bool ul() {
	return check(N+1,N+3);
}
bool ur() {
	return check(N+1,N+4);
}
bool dl() {
	return check(N+2,N+3);
}
bool dr() {
	return check(N+2,N+4);
}
bool lr() {
	return check(N+3,N+4);
}
//N+1 UpLim,N+2 DoLim,N+3 LeLim,N+4 RiLim
int l;
using namespace std;
signed main() {
	int i,j;
	scanf("%lld%lld%lld%lld",&N,&T,&n,&m);
	for(i=1; i<=N; i++) scanf("%lld%lld%lld",&a[i].x,&a[i].y,&a[i].r);
	for(i=1; i<=N; i++) for(j=i+1; j<=N; j++) b[++l]= (edge) {
			i,j,D(a[i],a[j])
		};
	for(i=1; i<=N; i++) b[++l]= (edge) {i,N+1,(double)m-a[i].y-a[i].r},b[++l]= (edge) {i,N+2,(double)a[i].y-a[i].r},b[++l]= (edge) {i,N+3,(double)a[i].x-a[i].r},b[++l]= (edge) {
		i,N+4,(double)n-a[i].x-a[i].r
	};
	sort(b+1,b+l+1,cmp);
	for(i=1; i<=N+4; i++) f[i]=i;
	for(i=1; i<=4; i++)for(j=1; j<=4; j++) r[i][j]=2e10;
	for(i=1; i<=l; i++) {
		uni(b[i].i,b[i].j);
		if((dl()||dr()||ud())&&fabs(r[1][2]-2e10)<1e-2) r[1][2]=b[i].d;
		if((dl()||ur()||ud()||lr())&&fabs(r[1][3]-2e10)<1e-2) r[1][3]=b[i].d;
		if((dl()||ul()||lr())&&fabs(r[1][4]-2e10)<1e-2) r[1][4]=b[i].d;
		if((dr()||ur()||lr())&&fabs(r[2][3]-2e10)<1e-2) r[2][3]=b[i].d;
		if((ul()||dr()||lr()||ud())&&fabs(r[2][4]-2e10)<1e-2) r[2][4]=b[i].d;
		if((ul()||ur()||ud())&&fabs(r[3][4]-2e10)<1e-2) r[3][4]=b[i].d;
	}
	for(i=1; i<=4; i++) for(j=1; j<i; j++) r[i][j]=r[j][i];
	while(T--) {
		scanf("%lld%lld",&n,&m);
		for(i=1; i<=4; i++) if(r[m][i]>=2*n) printf("%lld",i);
		printf("\n");
	}
	return 0;
}

Compilation message

park.cpp: In function 'int main()':
park.cpp:54:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |  scanf("%lld%lld%lld%lld",&N,&T,&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:55:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |  for(i=1; i<=N; i++) scanf("%lld%lld%lld",&a[i].x,&a[i].y,&a[i].r);
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |   scanf("%lld%lld",&n,&m);
      |   ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 605 ms 63244 KB Output is correct
2 Correct 643 ms 63236 KB Output is correct
3 Correct 596 ms 63252 KB Output is correct
4 Correct 603 ms 63308 KB Output is correct
5 Correct 592 ms 63236 KB Output is correct
6 Correct 620 ms 63248 KB Output is correct
7 Correct 629 ms 63232 KB Output is correct
8 Correct 636 ms 63232 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 2356 KB Output is correct
2 Correct 58 ms 2356 KB Output is correct
3 Correct 48 ms 2188 KB Output is correct
4 Correct 55 ms 2388 KB Output is correct
5 Correct 52 ms 2316 KB Output is correct
6 Correct 64 ms 2356 KB Output is correct
7 Correct 45 ms 1744 KB Output is correct
8 Correct 44 ms 1740 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 605 ms 63244 KB Output is correct
2 Correct 643 ms 63236 KB Output is correct
3 Correct 596 ms 63252 KB Output is correct
4 Correct 603 ms 63308 KB Output is correct
5 Correct 592 ms 63236 KB Output is correct
6 Correct 620 ms 63248 KB Output is correct
7 Correct 629 ms 63232 KB Output is correct
8 Correct 636 ms 63232 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 54 ms 2356 KB Output is correct
12 Correct 58 ms 2356 KB Output is correct
13 Correct 48 ms 2188 KB Output is correct
14 Correct 55 ms 2388 KB Output is correct
15 Correct 52 ms 2316 KB Output is correct
16 Correct 64 ms 2356 KB Output is correct
17 Correct 45 ms 1744 KB Output is correct
18 Correct 44 ms 1740 KB Output is correct
19 Correct 672 ms 64676 KB Output is correct
20 Correct 635 ms 64460 KB Output is correct
21 Correct 670 ms 64624 KB Output is correct
22 Correct 670 ms 64576 KB Output is correct
23 Correct 672 ms 64444 KB Output is correct
24 Correct 694 ms 64568 KB Output is correct