Submission #1105

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105		hana5505	개구리 (KOI13_frog)	C++98	16.94 / 22	1000 ms	2448 KiB

frog

#include<stdio.h>
struct pp{
	int x,y;
}ar[100001];
int n,r,d,que[100001],aa[100001];
int ok(int i,int j)
{
	int tmp;

	if(ar[i].x<=ar[j].x && ar[j].x<=ar[i].x+r){
		if(ar[i].y<=ar[j].y && ar[j].y<=ar[i].y+r+d) return 1;
		if(ar[i].y-r-d<=ar[j].y && ar[j].y<=ar[i].y) return 1;
	}
	if(ar[i].y<=ar[j].y && ar[j].y<=ar[i].y+r){
		if(ar[i].x<=ar[j].x && ar[j].x<=ar[i].x+r+d) return 1;
		if(ar[i].x-r-d<=ar[j].x && ar[j].x<=ar[i].x) return 1;
	}
	tmp=i;
	i=j;
	j=tmp;
	if(ar[i].x<=ar[j].x && ar[j].x<=ar[i].x+r){
		if(ar[i].y<=ar[j].y && ar[j].y<=ar[i].y+r+d) return 1;
		if(ar[i].y-r-d<=ar[j].y && ar[j].y<=ar[i].y) return 1;
	}
	if(ar[i].y<=ar[j].y && ar[j].y<=ar[i].y+r){
		if(ar[i].x<=ar[j].x && ar[j].x<=ar[i].x+r+d) return 1;
		if(ar[i].x-r-d<=ar[j].x && ar[j].x<=ar[i].x) return 1;
	}
	return 0;
}
int main()
{
	int i,st,head,tail,t,mx=0;

	scanf("%d %d",&n,&r);
	for(i=1;i<=n;i++){
		scanf("%d %d",&ar[i].x,&ar[i].y);
		if(ar[i].x==0 && ar[i].y==0) st=i;
	}
	scanf("%d",&d);

	que[1]=st;
	head=tail=1;
	aa[st]=1;
	while(head<=tail){
		t=que[head++];
		for(i=1;i<=n;i++){
			if(!aa[i] && ok(t,i)){
				aa[i]=1;
				que[++tail]=i;
			}
		}
	}

	for(i=1;i<=n;i++){
		if(aa[i] && ar[i].x+ar[i].y>mx) mx=ar[i].x+ar[i].y;
	}

	printf("%d",mx+2*r);
}

• Subtask 1: 1.98 / 1.98
• Subtask 2: 2.64 / 2.64
• Subtask 3: 3.52 / 3.52
• Subtask 4: 4.18 / 4.18
• Subtask 5: 4.62 / 4.62
• Subtask 6: 0 / 5.06