답안 #1105

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1105	2013-06-25T08:28:37 Z	hana5505	개구리 (KOI13_frog)	C++	16.94 / 22	1000 ms	2448 KB

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

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	2448 KB	Output is correct
2	Correct	0 ms	2448 KB	Output is correct
3	Correct	0 ms	2448 KB	Output is correct
4	Correct	0 ms	2448 KB	Output is correct
5	Correct	0 ms	2448 KB	Output is correct
6	Correct	1 ms	2448 KB	Output is correct
7	Correct	0 ms	2448 KB	Output is correct

Subtask #2

2.64 / 2.64

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	2448 KB	Output is correct
2	Correct	0 ms	2448 KB	Output is correct
3	Correct	0 ms	2448 KB	Output is correct
4	Correct	0 ms	2448 KB	Output is correct
5	Correct	0 ms	2448 KB	Output is correct
6	Correct	0 ms	2448 KB	Output is correct
7	Correct	0 ms	2448 KB	Output is correct

Subtask #3

3.52 / 3.52

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	2448 KB	Output is correct
2	Correct	0 ms	2448 KB	Output is correct
3	Correct	0 ms	2448 KB	Output is correct
4	Correct	0 ms	2448 KB	Output is correct
5	Correct	1 ms	2448 KB	Output is correct
6	Correct	111 ms	2448 KB	Output is correct
7	Correct	109 ms	2448 KB	Output is correct

Subtask #4

4.18 / 4.18

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2448 KB	Output is correct
2	Correct	13 ms	2448 KB	Output is correct
3	Correct	14 ms	2448 KB	Output is correct
4	Correct	63 ms	2448 KB	Output is correct
5	Correct	37 ms	2448 KB	Output is correct
6	Correct	172 ms	2448 KB	Output is correct
7	Correct	174 ms	2448 KB	Output is correct

Subtask #5

4.62 / 4.62

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	2448 KB	Output is correct
2	Correct	1 ms	2448 KB	Output is correct
3	Correct	61 ms	2448 KB	Output is correct
4	Correct	6 ms	2448 KB	Output is correct
5	Correct	274 ms	2448 KB	Output is correct
6	Correct	452 ms	2448 KB	Output is correct
7	Correct	450 ms	2448 KB	Output is correct

Subtask #6

0.0 / 5.06

#	결과	실행 시간	메모리	Grader output
1	Correct	768 ms	2448 KB	Output is correct
2	Execution timed out	1000 ms	2448 KB	Program timed out
3	Halted	0 ms	0 KB	-
4	Halted	0 ms	0 KB	-
5	Halted	0 ms	0 KB	-
6	Halted	0 ms	0 KB	-
7	Halted	0 ms	0 KB	-