Page 1 of 2
10158 - War
Posted: Thu Jan 22, 2004 5:13 pm
by 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!!
Posted: Sun Jun 19, 2005 3:54 pm
by 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.
Posted: Wed May 02, 2007 3:35 pm
by 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...
Posted: Wed May 02, 2007 8:25 pm
by 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
Hope it helps.
Posted: Thu May 03, 2007 7:11 am
by 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?
Posted: Thu May 03, 2007 1:24 pm
by Jan
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
Hope it helps.
Posted: Thu May 03, 2007 2:23 pm
by 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
Posted: Wed May 16, 2007 12:29 pm
by 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;
}
Posted: Wed May 16, 2007 7:48 pm
by Jan
Try the set below.
Input:
Output:
Hope it helps.
Posted: Mon Jul 02, 2007 9:01 pm
by 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);
}
}
Re: 10158 - War
Posted: Fri Sep 04, 2009 12:17 pm
by 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:
The output should be:
-1
Hope it helps
Re: 10158 - War
Posted: Sat Sep 12, 2009 3:41 pm
by 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.
Re: 10158 - War
Posted: Sun Mar 21, 2010 12:49 pm
by Angeh
Hi all ,
would sombody how has solved the problem give some hints ...
Re: 10158 - War
Posted: Sat Jul 03, 2010 1:55 am
by amishera
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
by 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.