10158 - War

[DJYA]

Hello everybody~

I'm trying to solve problem 10158 but always get TLE.

This problem should be about "disjiont set".
But it's like to think about so many conditions .

Could someone tell me how to solve this problem in detail ??

THX!!

[danielrocha]

It is indeed a problem about "Disjoint Sets". I'll give you a small clue: at any given time a person X can be enemies with only one (or zero) group of friends Y. Never more than that.

[hi!man!]

I always got WA in this problem...
can anyone help me??? thanks.

a[] records friend relationship
b[] records enemy relationship

maybe I miss something...

Code: Select all

ACed

[Jan]

Try the case.

Input:

Code: Select all

10
2 7 4
1 9 4
3 8 2
1 5 5
2 7 1
4 5 2
4 6 1
1 2 3
1 2 1
1 8 5
4 6 1
3 9 2
4 9 5
3 3 1
3 3 3
1 1 1
0 0 0

Output:

Code: Select all

0
0
0
0
1
0
1
1

Hope it helps.

[hi!man!]

after I modify my code
still WA
I think that it should not have a "s" in setFriend()
but when I remove it
I got RE..is this because stack overflow?

Code: Select all

ACed

[Jan]

I think that it should not have a "s" in setFriend()

I don't understand what you are mentioning. However test the set...

Input:

Code: Select all

10
4 4 0
2 4 8
3 2 4
2 5 1
4 1 1
4 2 7
1 1 4
3 3 2
3 1 6
3 5 7
3 1 8
2 2 7
4 5 4
4 1 2
2 3 4
2 1 3
1 7 4
3 7 7
4 3 1
2 8 6
0 0 0

Output:

Code: Select all

0
0
0
0
0
0
0
0
1
0
1
1

Hope it helps.

[hi!man!]

thanks for your help~
I got AC
the main reason I got WA is that b[] has some problem..

btw, I don't know how to explain "s" meaning..
(sorry for my poor English)
however, it is not important now

[jpeanut]

I passed all the test code

BUT Still Wa could someone tell me where is wrong

Code: Select all

#include <stdio.h>

int main(){
int f[10000];   
int kind,b,c;
int people=0;
int count=1;


   scanf("%d",&people);
   for(int i=0;i<people;i++)f[i]=0;
   scanf("%d %d %d",&kind,&b,&c);

   while ((kind!=0)||(b!=0)||(c!=0)){
    
     if(kind==1){
         if (f[b]==0&&f[c]==0){
            f[b]=count;
            f[c]=count;
            count++; 
                 }
         else if (f[b]!=0&&f[c]==0) f[c]=f[b];
         else if (f[c]!=0&&f[b]==0) f[b]=f[c];
         else if (f[b]!=f[c]&&f[b]!=-f[c]) for(int i=0;i<people;i++){if(f[i]==f[c])f[i]=f[b];
                                                                     if(f[i]==-f[c])f[i]=-f[b];}
             
         else if (f[c]==-f[b]) printf("-1\n");
      }

     if(kind==2){
       if(f[b]==f[c]){
         if (f[b]==0&&f[c]==0){
               f[b]=count;
               f[c]=0-count;
               count++;               
                  }
         else printf("-1\n");
          }
       else if (f[b]!=0&&f[c]==0) f[c]=-f[b];
       else if (f[c]!=0&&f[b]==0) f[b]=-f[c];
       else if (f[b]!=f[c]&&f[b]!=-f[c]) for(int i=0;i<people;i++){if(f[i]==f[c])f[i]=-f[b];
                                                                   if(f[i]==-f[c])f[i]=f[b];}
      }


     if(kind==3){
          if (f[b]==f[c]&&f[b]!=0&&f[c]!=0) printf("1\n");
          else printf("0\n");
        }

     if(kind==4){
          if (f[b]==-f[c]&&f[b]!=0&&f[c]!=0) printf("1\n");
          else printf("0\n");
        }

     scanf("%d %d %d",&kind,&b,&c);
}
return 0;
}

[Jan]

Try the set below.

Input:

Code: Select all

5
2 3 3
0 0 0

Output:

Code: Select all

-1

Hope it helps.

[renato_ferreira]

Now I got RE (Signal 11)

Code: Select all

#include <stdio.h>

int *pai, *rank, *flag, pessoas;

void MakeSet(int x);
int FindSet(int x);
void Union(int x, int y);
void Separa(int x, int y);

int main()
{
    int comando, n1, n2, i;

    scanf("%d", &pessoas);

    pai = calloc(pessoas, sizeof(int));
    rank = calloc(pessoas, sizeof(int));
    flag = calloc(pessoas, sizeof(int));

    for (i = 0; i < pessoas; i++)
    {
        MakeSet(i);
    }

    while (scanf("%d %d %d", &comando, &n1, &n2))
    {
        if (comando == 0)
        {
            break;
        }

        n1 = FindSet(n1);
        n2 = FindSet(n2);

        if (comando == 1)
        {
            if (flag[n1] == n2)
            {
                printf("-1\n");
            }

            else
            {
                Union(n1, n2);
            }
        }

        else if (comando == 2)
        {
            if (n1 == n2)
            {
                printf("-1\n");
            }

            else
            {
                Separa(n1, n2);
            }
        }

        else if (comando == 3)
        {
            for (i = 0; i < pessoas; i++)
            {
                if (flag[n1] == i && flag[n2] == i)
                {
                    n1 = n2;

                    break;
                }
            }

            if (n1 != n2)
            {
                printf("0\n");
            }

            else
            {
                printf("1\n");
            }
        }

        else
        {
            if (flag[n1] != n2)
            {
                printf("0\n");
            }

            else
            {
                printf("1\n");
            }
        }
    }

    return 0;
}

void MakeSet(int x)
{
    pai[x] = x;
    rank[x] = 1;
    flag[x] = -1;
}

int FindSet(int x)
{
    if (x != pai[x])
    {
        pai[x] = FindSet(pai[x]);
    }

    return pai[x];
}

void Union(int x, int y)
{
    int i;

    if (x == y)
    {
        return;
    }

    if (rank[x] > rank[y])
    {
        pai[x] = y;
        rank[y] += rank[x];

        for (i = 0; i < pessoas; i++)
        {
            if (flag[x] == i)
            {
                flag[y] = i;
                flag[i] = y;
            }
        }
    }

    else
    {
        pai[y] = x;
        rank[x] += rank[y];

        for (i = 0; i < pessoas; i++)
        {
            if (flag[y] == i)
            {
                flag[x] = i;
                flag[i] = x;
            }
        }
    }
}

void Separa(int x, int y)
{
    if (flag[x] == -1 && flag[y] == -1)
    {
        flag[x] = y;
        flag[y] = x;
    }

    else
    {
        Union(flag[x], y);
        Union(flag[y], x);
    }
}

[Articuno]

Can anyone give me some more critical test cases? I am getting WA and I can't find my error. Someone please help.....
Here is my code:
AC
Here is a test case:

Code: Select all

5
1 0 1
1 2 3
2 1 3
1 0 2
0 0 0

The output should be:
-1
Hope it helps

[calicratis19]

can anyone please discuss how to solve this problem. i cant figure out how to do it with union find.

i figured out how to mark enemies.but couldnt figured out how to find common enemies.

any help will be appreciated .thank you.

[Angeh]

Hi all ,
would sombody how has solved the problem give some hints ...

[amishera]

You have to use disjoint set forest algorithm. Or you can also use binary search tree. I think disjoint forest would be faster.

[csprajeeth]

For those getting runtime error.... most likely you are overflowing the stack (due to unbounded recursion). Check if you are introducing cycles in your disjoint set data structure.