| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
麻烦帮忙看下,这题不就是并查集吗,why TLE?#include<iostream>
using namespace std;
const int N = 1001;
bool flag[N][N];
int n,d;
bool used[N];
struct POINT
{
int x,y;
};
POINT point[N];
struct COMPUTER
{
int parent;
int rank;
};
COMPUTER computer[N];
void initial(int n)
{
int i;
for (i=1;i<=n;i++)
{
computer[i].parent = i;
computer[i].rank = 0;
}
}
int find_set(int x)
{
int p = x;
while (computer[x].parent != x)
{
x = computer[x].parent;
}
while (computer[p].parent != x)
{
computer[p].parent = x;
p = computer[p].parent;
}
return x;
}
void union_set(int x,int y)
{
x = find_set(x);
y = find_set(y);
if(computer[x].rank > computer[y].rank)
{
computer[y].parent = x;
}
else
{
computer[x].parent = y;
if(computer[x].rank == computer[y].rank)
computer[y].rank++;
}
}
int main()
{
int i,j,dis,p,q;
char ch[2];
scanf("%d%d",&n,&d);
initial(n);
d = d*d;
for(i=1;i<=n;i++)
{
scanf("%d%d",&point[i].x,&point[i].y);
}
memset(flag,false,sizeof(flag));
memset(used,false,sizeof(used));
for(i=1;i<=n;i++)
{
for (j=i+1;j<=n;j++)
{
dis = (point[i].x - point[j].x)*(point[i].x - point[j].x)+(point[i].y - point[j].y)*(point[i].y - point[j].y);
if( dis <= d )
flag[i][j] = flag[j][i] = true;
}
}
while (1)
{
/*
getchar();
if(scanf("%c",ch)!=1)
break;*/
while(scanf("%s",ch) != EOF )
{
if(ch[0] == 'O')
{
scanf("%d",&p);
used[p] = true;
for(i=1;i<=n;i++)
{
if(i!=p && used[i] && flag[p][i])
{
union_set(p,i);
}
}
}
else
{
scanf("%d%d",&p,&q);
p = find_set(p);
q = find_set(q);
if(p==q)
printf("SUCCESS\n");
else
printf("FAIL\n");
}
}
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator