| ||||||||||
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 |
这题居然能暴力!!!4000ms啊。。。一点没优化都过了#include<stdio.h> #include<string.h> using namespace std; int pre[1005]; int n,d; void init(){ for(int i=1;i<=n;i++) pre[i]=i; } int find(int x){ while(x!=pre[x]) x=pre[x]; return x; } struct node { int x,y,id,vis;}a[1010]; bool dis(int i,int j) { if(((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y))>d*d) return false; else return true; } int main(){ scanf("%d%d",&n,&d); init(); for(int i=1;i<=n;i++){ scanf("%d%d",&a[i].x,&a[i].y); a[i].id=i; a[i].vis=0; } char s[5]; int v,u; while(scanf("%s",&s)!=EOF){ if(s[0]=='S'){ scanf("%d%d",&v,&u); int dx=find(v); int dy=find(u); if(pre[dx]!=pre[dy]) printf("FAIL\n"); else printf("SUCCESS\n"); } if(s[0]=='O'){ scanf("%d",&v); a[v].vis=1; int dx=find(v); for(int i=1;i<=n;i++){ if(a[i].vis&&dis(v,i)&&v!=i){ int dy=find(i); if(dx!=dy){ pre[dy]=dx; } } } } } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator