| ||||||||||
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