Page 1 of 2

### 10158 - War

Posted: Thu Jan 22, 2004 5:13 pm
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!!

Posted: Sun Jun 19, 2005 3:54 pm
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.

Posted: Wed May 02, 2007 3:35 pm
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``

Posted: Wed May 02, 2007 8:25 pm
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.

Posted: Thu May 03, 2007 7:11 am
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``

Posted: Thu May 03, 2007 1:24 pm
hi!man! wrote: 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.

Posted: Thu May 03, 2007 2:23 pm
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 Posted: Wed May 16, 2007 12:29 pm
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;
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;
}``````

Posted: Wed May 16, 2007 7:48 pm
Try the set below.

Input:

Code: Select all

``````5
2 3 3
0 0 0``````
Output:

Code: Select all

``-1``
Hope it helps.

Posted: Mon Jul 02, 2007 9:01 pm
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);
}
}
``````

### Re: 10158 - War

Posted: Fri Sep 04, 2009 12:17 pm
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

### Re: 10158 - War

Posted: Sat Sep 12, 2009 3:41 pm
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.

### Re: 10158 - War

Posted: Sun Mar 21, 2010 12:49 pm
Hi all ,
would sombody how has solved the problem give some hints ... ### Re: 10158 - War

Posted: Sat Jul 03, 2010 1:55 am
You have to use disjoint set forest algorithm. Or you can also use binary search tree. I think disjoint forest would be faster.

### Re: 10158 - War

Posted: Sat Dec 28, 2013 11:04 pm
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.