Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:WA的童鞋进!!!!(附代码)

Posted by XKing at 2014-10-14 20:06:46 on Problem 1703
In Reply To:WA的童鞋进!!!!(附代码) Posted by:speedcell4 at 2011-08-01 21:45:17
> 测下这组数据
> 1
> 2 1
> A 1 2
> 答案应该是In different gangs.
> 就因为这个……WA到死……
> 
> #include<iostream>
> #define SIZE 100010
> using namespace std;
> int tcase;
> int n,m,x,y;
> char ctrl;
> struct node
> {
>     int pa;
>     int ki;
> }a[SIZE];
> void Init(int n)
> {
>     for(int i=1;n-i>=0;i++)
>     {
>         a[i].pa=i;
>         a[i].ki=0;
>     }
> }
> int findPa(int n)
> {
>     if(a[n].pa!=n)
>     {
>         int Pa=a[n].pa;
>         int Root=findPa(a[n].pa);
>         a[n].ki=(a[n].ki+a[Pa].ki)%2;
>         return a[n].pa=Root;
>     }
>     else return n;
> }
> void Union(int x,int y)
> {
>     int xx=findPa(x);
>     int yy=findPa(y);
>     a[xx].pa=yy;
>     a[xx].ki=(a[y].ki-a[x].ki+1+2)%2;
> }    
> int main()
> {
>     scanf("%d",&tcase);while(tcase--)
>     {
>         scanf("%d %d",&n,&m);getchar();
>         Init(n);
>         for(int i=0;m-i>0;i++)
>         {
>             scanf("%c %d %d",&ctrl,&x,&y);getchar();
>             if(n==2&&ctrl=='A') printf("In different gangs.\n");
>             else if(ctrl=='D')
>             {
>                 Union(x,y);
>             }
>             else
>             {
>                 int xx=findPa(x);
>                 int yy=findPa(y);
>                 if(xx!=yy) printf("Not sure yet.\n");
>                 else if(a[x].ki==a[y].ki) printf("In the same gang.\n");
>                 else printf("In different gangs.\n");
>             }
>         }
>     }
>     return 0;
> } 

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator