## 10158 - War

All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

DJYA
New poster
Posts: 7
Joined: Sat Jan 10, 2004 10:18 pm

### 10158 - War

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
New poster
Posts: 44
Joined: Sun Apr 27, 2003 3:17 am
Location: Rio Grande do Norte - Brazil
Contact:
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.
Daniel
UFRN HDD-1
Brasil

hi!man!
New poster
Posts: 48
Joined: Fri Dec 29, 2006 1:26 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``
Last edited by hi!man! on Thu May 03, 2007 2:18 pm, edited 1 time in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:
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.
Ami ekhono shopno dekhi...
HomePage

hi!man!
New poster
Posts: 48
Joined: Fri Dec 29, 2006 1:26 pm
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``
Last edited by hi!man! on Thu May 03, 2007 2:18 pm, edited 1 time in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:
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.
Ami ekhono shopno dekhi...
HomePage

hi!man!
New poster
Posts: 48
Joined: Fri Dec 29, 2006 1:26 pm
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
New poster
Posts: 1
Joined: Fri May 11, 2007 7:33 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[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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:
Try the set below.

Input:

Code: Select all

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

Code: Select all

``-1``
Hope it helps.
Ami ekhono shopno dekhi...
HomePage

renato_ferreira
New poster
Posts: 21
Joined: Thu Jun 14, 2007 11:45 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);
}
}
``````

Articuno
Learning poster
Posts: 78
Joined: Sun Nov 30, 2008 5:00 pm
Location: IUT-OIC, Dhaka, Bangladesh

### Re: 10158 - War

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
Last edited by Articuno on Sun Nov 15, 2009 10:55 pm, edited 1 time in total.

calicratis19
Learning poster
Posts: 76
Joined: Mon Jul 21, 2008 8:50 am
Location: SUST,SYLHET,BANGLADESH.
Contact:

### Re: 10158 - War

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.
Heal The World

Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

### Re: 10158 - War

Hi all ,
would sombody how has solved the problem give some hints ...
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

amishera
New poster
Posts: 38
Joined: Sat Dec 27, 2008 10:42 pm

### Re: 10158 - War

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

csprajeeth
New poster
Posts: 5
Joined: Sat May 26, 2012 7:25 pm

### Re: 10158 - War

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.