TOJ 89

domen111

http://toj.tfcis.org/oj/pro/89/
這筆測資的答案是先nope再yeap沒錯吧? 怎麼標準解答的答案不一樣
我自己產的測資:

1. !
   
2. 10
   
3. you are friends 1 2
   
4. you are friends 5 6
   
5. you are friends 3 4
   
6. you are friends 2 3
   
7. you are enemies 4 5
   
8. you are friends 10 9
   
9. are you friends 4 6
   
10. are you enemies 4 6

複製代碼

我的程式的輸出:

1. !
   
2. yeap
   
3. nope

複製代碼

標準程式的輸出:

1. !
   
2. nope
   
3. yeap

複製代碼

allenwhale

sorry 標程打錯字了... 謝謝提醒 已修正

domen111

剛剛花了整個下午在debug這題
就只是60行的一個bug，大概就前面改到了陣列後面卻繼續用的bug，先拿個變數存著就解決了，不過這種bug好難抓喔
學長的code漂亮多了，行數將近我的一半，值得觀摩一下啊!

Sylveon

學長，disjoin set 的union又寫錯了 TAT，跟NPSC一樣，測資不夠強歐~

@FIXED

#include <stdio.h>

#include <string.h>

#define R(x) (x+N)

#define MAXN 500010

int p[MAXN*2];

int N;

void init()

{

    for(int i=0;i<=2*N;i++)p[i]=i;

}

int find(int x)

{

    //printf(" %d\n",x);

    return x==p[x]?x:p[x]=find(p[x]);

}

void U(int a,int b)

{

//    printf("U %d %d %d %d\n",a,find(a),b,find(b));

    p[find(a)]=find(b);

}

int main()

{

    //memset(p,0,sizeof(p));

    scanf("%d",&N);

    init();

   

    int a,b;

    char s[3][10];

    while(~scanf("%s %s %s %d %d",s[0],s[1],s[2],&a,&b))

    {

        int aa=find(a),bb=find(b);

        int ra=find(a+N),rb=find(b+N);

        //printf("    %d %d %d %d\n",aa,ra,bb,rb);

        if(strcmp(s[0],"you")==0&&strcmp(s[2],"friends")==0)//sf

        {

            if(aa==rb)puts("angry");

            else U(aa,bb),U(ra,rb);

        }

        else if(strcmp(s[0],"you")==0&&strcmp(s[2],"enemies")==0)//se

        {

            if(aa==bb)puts("angry");

            else U(aa,rb),U(bb,ra);

        }

        else if(strcmp(s[0],"are")==0&&strcmp(s[2],"friends")==0)//af

        {

            if(aa==bb)puts("yeap");

            else puts("nope");

        }

        else if(strcmp(s[0],"are")==0&&strcmp(s[2],"enemies")==0)//ae

        {

            if(aa==rb)puts("yeap");

            else puts("nope");

        }

        //print();

    }

    return 0;

}