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 |
呵呵,此题数据太弱。你的蒙分算法如下吧~In Reply To:惊讶:蒙分算法0ms过! Posted by:AllwaysDead at 2008-09-29 17:30:46 #include <cstdio> #include <string.h> using namespace std; int father[10000]; int findfather(int a){return father[a]==-1?a:father[a]=findfather(father[a]);} void together(int a,int b){if (findfather(a)!=findfather(b))father[findfather(a)]=findfather(b);} int map1[100][100],map2[100][100],map3[100][100],W,H,colors1[10000][6],colors2[10000][6]; int T2(int a){return a*a;} int Minn(int a,int b){if (a<b)return T2(b);return T2(a);} int main(){ int N,s,i,x,y,j; scanf("%d",&N); while (N--){ memset(map1,0,sizeof(map1));memset(map2,0,sizeof(map2)); scanf("%d %d %d",&W,&H,&s); for (i=0;i<s;i++){scanf("%d %d",&x,&y);map1[y][x]=-1;} for (i=0;i<s;i++){scanf("%d %d",&x,&y);map2[y][x]=-1;} memset(father,0xff,sizeof(father)); for (x=0;x<H;x++)for (y=0;y<W;y++)if (map1[x][y]){ if (x>0 && map1[x-1][y])together(x*100+y,(x-1)*100+(y)); if (y>0 && map1[x][y-1])together(x*100+y,(x)*100+(y-1)); if (x+1<H && map1[x+1][y])together(x*100+y,(x+1)*100+(y)); if (y+1<W && map1[x][y+1])together(x*100+y,(x)*100+(y+1)); } memset(colors1,0xff,sizeof(colors1)); for (x=0;x<H;x++)for (y=0;y<W;y++)if (map1[x][y]){i=map1[x][y]=findfather(x*100+y)+1;i--; colors1[i][0]++; if (colors1[i][1]==-1 || colors1[i][1]>x)colors1[i][1]=x; if (colors1[i][2]==-1 || colors1[i][2]<x)colors1[i][2]=x; if (colors1[i][3]==-1 || colors1[i][3]>y)colors1[i][3]=y; if (colors1[i][4]==-1 || colors1[i][4]<y)colors1[i][4]=y; } for (x=0;x<H;x++)for (y=0;y<W;y++)if ((i=map1[x][y]-1)>=0) colors1[i][5]+=Minn(x-colors1[i][1],colors1[i][2]-x)+Minn(y-colors1[i][3],colors1[i][4]-y); memset(father,0xff,sizeof(father)); for (x=0;x<H;x++)for (y=0;y<W;y++)if (map2[x][y]){ if (x>0 && map2[x-1][y])together(x*100+y,(x-1)*100+(y)); if (y>0 && map2[x][y-1])together(x*100+y,(x)*100+(y-1)); if (x+1<H && map2[x+1][y])together(x*100+y,(x+1)*100+(y)); if (y+1<W && map2[x][y+1])together(x*100+y,(x)*100+(y+1)); } memset(colors2,0xff,sizeof(colors2)); for (x=0;x<H;x++)for (y=0;y<W;y++)if (map2[x][y]){i=map2[x][y]=findfather(x*100+y)+1;i--; colors2[i][0]++; if (colors2[i][1]==-1 || colors2[i][1]>x)colors2[i][1]=x; if (colors2[i][2]==-1 || colors2[i][2]<x)colors2[i][2]=x; if (colors2[i][3]==-1 || colors2[i][3]>y)colors2[i][3]=y; if (colors2[i][4]==-1 || colors2[i][4]<y)colors2[i][4]=y; } for (x=0;x<H;x++)for (y=0;y<W;y++)if ((i=map2[x][y]-1)>=0) colors2[i][5]+=Minn(x-colors2[i][1],colors2[i][2]-x)+Minn(y-colors2[i][3],colors2[i][4]-y); for (x=0;x<10000;x++)if (colors1[x][0]!=-1){ colors1[x][2]-=colors1[x][1]; colors1[x][4]-=colors1[x][3]; if (colors1[x][4]<colors1[x][2]){y=colors1[x][4];colors1[x][4]=colors1[x][2];colors1[x][2]=y;} } for (x=0;x<10000;x++)if (colors2[x][0]!=-1){ colors2[x][2]-=colors2[x][1]; colors2[x][4]-=colors2[x][3]; if (colors2[x][4]<colors2[x][2]){y=colors2[x][4];colors2[x][4]=colors2[x][2];colors2[x][2]=y;} } for (j=0;j<10000;j++)if (colors1[j][0]!=-1){ for (i=0;i<10000 && (!(colors1[j][0]==colors2[i][0] && colors1[j][2]==colors2[i][2] && colors1[j][4]==colors2[i][4] && colors1[j][5]==colors2[i][5]));i++); if (i==10000){puts("NO");break;} colors2[i][0]=-1; } if (j==10000)puts("YES"); } getchar();getchar();getchar(); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator