| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1105 |
2013-06-25T08:28:37 Z |
hana5505 |
개구리 (KOI13_frog) |
C++ |
|
1000 ms |
2448 KB |
#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);
}
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
