## 10505 - Montesco vs Capuleto

Moderator: Board moderators

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
yiuyuho wrote: Doesn't that mean the components of the given graphs are all bipartite? But the test case 3 does not satisfy that...
That case, we cannot invite anyone from that component..

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:
Well, what I am saying is the problem doesn't say what it means very nicely.
The given graph (Case 3) doesn't satisfy anti-transitive, it's something we have to check (not a property of the given graph)... But at the same time the symmetric relation is given in the same format and that's a property of the given graph...

You know what I mean?

Young20
New poster
Posts: 5
Joined: Fri Jul 06, 2007 6:39 pm
I'm trying to solve this problem.
I passed all above test case. HOWEVER I still got Wrong Answer..
I really don't know why.. so I wonder there are some tricky input test case..
Anyway, would someone give me correct output regarding input below?
Input..

Code: Select all

``````2

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

20
3 2 3 4
0
0
0
``````
Output

Code: Select all

``````0
19
``````
Thanks

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
My AC code gives the same output..

Young20
New poster
Posts: 5
Joined: Fri Jul 06, 2007 6:39 pm
Hmm..
I almost exhausted.. I have no idea why I got WA..
Could somebody give me a little hint?

My code below and my algorithm like that.
1. build bipartite graph(like tree structure)
2. if there need to combine each other trees, make one tree.
3. print out maximum number of invitation.

Code: Select all

``````#include <iostream>
#include <stdio.h>
#include <memory.h>
#include <string>
#include <strstream>
using namespace std;

#define MAXN	220
typedef struct {
int NrFriend, NrEnermy, illegal;
} Group;

int bipartite[MAXN][2];
int depth[MAXN];
Group g[MAXN];
int N;

int set_enermy(int x, int y)
{
int a,b,r1,r2;

for (a = x, r1 = 0; bipartite[a][0] != -1; r1 += bipartite[a][1], a = bipartite[a][0]);
for(b = y, r2 = 0; bipartite[b][0] != -1; r2 += bipartite[b][1], b = bipartite[b][0]);

if (a==b && (r1+r2)%2 != 1) {
g[a].illegal = 1;
return 0;
}

if (a != b) {
if (depth[a] < depth[b]) {
bipartite[a][0] = b;
bipartite[a][1] = (r1+r2+1)%2;
if (bipartite[a][1] % 2 == bipartite[b][1] % 2) {
g[b].NrEnermy += g[a].NrEnermy;
g[b].NrFriend += g[a].NrFriend;
} else {
g[b].NrEnermy += g[a].NrFriend;
g[b].NrFriend += g[a].NrEnermy;
}
} else {
bipartite[b][0] = a;
bipartite[b][1] = (r1+r2+1)%2;
if (bipartite[a][1] % 2 == bipartite[b][1] % 2) {
g[a].NrEnermy += g[b].NrEnermy;
g[a].NrFriend += g[b].NrFriend;
} else {
g[a].NrEnermy += g[b].NrFriend;
g[a].NrFriend += g[b].NrEnermy;
}
if (depth[a] == depth[b]) {
depth[a]++;
}
}
}

return 0;
}

int main()
{
int i,j,k,testcase,maxinvitation;
char buffer[200];

do {
cin.getline(buffer,200);
} while (buffer[0] == '\n' || buffer[0] == '\0');
istrstream strin(buffer);
strin >> testcase;
while (testcase--) {
do {
cin.getline(buffer,200);
} while (buffer[0] == '\n' || buffer[0] == '\0');
istrstream strin1(buffer);
strin1 >> N;

for (i = 1; i <= 200; i++) {
bipartite[i][0] = -1;
bipartite[i][1] = 0;
depth[i] = 0;
g[i].NrEnermy = 0;
g[i].NrFriend = 1;
g[i].illegal = 0;
}

i = 1;
do {
cin.getline(buffer, 200);
if (buffer[0] == '\n' || buffer[0] == '\0') break;

istrstream strin2(buffer);
strin2 >> k;

while (k-- > 0 && !strin2.eof()) {
j = -1;
strin2 >> j;
if (i <= N && j != -1 && j <= N) {
set_enermy(i,j);
}
}
} while (i++);

// printout
maxinvitation = 0;
for (i = 1; i<= N; i++) {
if (bipartite[i][0] == -1 && g[i].illegal == 0) {
maxinvitation += (g[i].NrEnermy > g[i].NrFriend)? g[i].NrEnermy : g[i].NrFriend;
}
}
cout << maxinvitation << endl;
}
return 0;
}

``````
Thanks
Last edited by Young20 on Sat Jul 07, 2007 2:53 am, edited 1 time in total.

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Code: Select all

``   char buffer[200];  ``
is clearly not enough, as the problem are of order 200.

Also, I am not sure what your setEnemy is doing, what's r1, r2?

Young20
New poster
Posts: 5
Joined: Fri Jul 06, 2007 6:39 pm
Hello

first of all, it has type error. These two line should be changed like that

Code: Select all

``````	for (a = x, r1 = 0; bipartite[a][0] != -1; r1 +=bipartite[a][1], a = bipartite[a][0]);
for (b = y, r2 = 0; bipartite[b][0] != -1; r2 +=bipartite[b][1], b = bipartite[b][0]);
``````
But still got WA.. even though I extended the size of buffer rather than 200.

Code: Select all

``````char buffer[1000];
``````
setEnermy function is doing like that
if x, y is enermy, a became root of b with relation value(bipartite[1])-that is combining two diffrent graph.
As you can see, a and b is root of x and y. And you can collect r1, r2 that climb up to parent node.
if bipartite[1] is 0 that means b has same color with its parent. if bipartite[1] has 1, b has diffrent color with its parent.

Thanks

Young20
New poster
Posts: 5
Joined: Fri Jul 06, 2007 6:39 pm
Hmm..
It makes me crazy.

Code: Select all

``````1

100
2 23
0
0
3 3 8 11
3 8 11 13
1 11
1 13
2 4 5
2 18 13
3 20 18 21
3 4 5 6
1 21
0
0
0
0
1 21
2 9 10
1 21
0
4 12 17 19 25
0
0
2 25 27
4 21 22 23 24
0
2 24 26
0
3 30 37 38
3 26 28 29
0
0
0
0
0
0
1 29
2 29 31
1 40
3 31 39 51
0
0
0
0
0
0
0
0
0
0
0
0
2 58 59
0
0
1 79
2 51 52
2 53 52
1 53
0
0
0
0
0
0
0
0
0
0
0
1 53
0
1 79
0
1 53
0
0
0
1 53 54 55 56 70 72 73
0
0
0
0
3 73 74 76
0
3 76 77 83
2 90 100
1 83
0
3 83 85 87
0
0
0
0
0
0
0
0
0
2 87 89

``````
my output like that

Code: Select all

``````73
``````
Am I right?

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

shakil
Learning poster
Posts: 74
Joined: Sat Jul 15, 2006 6:28 am
Contact:
Why WA!!!!!! I check all sample input and output in the post but can not find the cause of WA. Please help......

Code: Select all

``````#include<stdio.h>
long n,sa[209][209],x[209],y[209],z[209],si[209];
void make(long h1,long h2)
{
long X,Y,i;
X=0;
Y=0;

for(i=1;i<=n;i++)
{if(sa[h2][i]==1&&si[i]==1)
X=1;
else if(sa[h2][i]==1&&si[i]==2)
Y=1;}
if(X==1&&Y==1)
{z[h1]=1;si[h2]=1;}
else if(X==1)
{y[h1]++;si[h2]=2;}
else
{x[h1]++;si[h2]=1;}

for(i=1;i<=n;i++)
if(sa[h2][i]==1&&si[i]==0)
make(h1,i);

}

void main()
{

long cas,cas1,m,i,j,sum,a,b;

scanf("%ld",&cas);

for(cas1=1;cas1<=cas;cas1++)
{

scanf("%ld",&n);

for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
sa[i][j]=0;

for(i=1;i<=n;i++)
si[i]=0;

for(i=1;i<=n;i++)
{
scanf("%ld",&a);
for(j=0;j<a;j++)
{
scanf("%ld",&b);
if(b<=n)
{
sa[i][b]=1;
sa[b][i]=1;
}
}
}

m=0;
for(i=1;i<=n;i++)
if(si[i]==0)
{
x[m]=1;
y[m]=0;
z[m]=0;
si[i]=1;
for(j=1;j<=n;j++)
if(sa[i][j]==1&&si[j]==0)
make(m,j);
m++;
}

for(i=0;i<m;i++)
if(y[i]>x[i])
x[i]=y[i];
sum=0;

for(i=0;i<m;i++)
if(z[i]==0)
sum+=x[i];

printf("%ld\n",sum);

}
}``````
SHAKIL

withelm
New poster
Posts: 1
Joined: Sat Dec 24, 2011 1:52 am

### Re: 10505 - Montesco vs Capuleto

Yo,
I check all in/out but I do not know why is WA

Code: Select all

``````#include <cstdio>
#include <vector>

using namespace std;

const int MX = 300;

bool v[MX];
vector <int> gr[MX];
int kolor[MX];

int n,m,a,b,c,wynik;

void clear()
{
for(int i=0;i<MX;i++)
{
v[i] = false;
gr[i].clear();
kolor[i] = 3;
}
wynik = 0;
}

int bfs(int x)
{
vector <int> kolejka;
kolejka.push_back(x);
v[x] = true;
kolor[x] = 1;
int red = 0;
int blue = 0;
int next;
bool ok = false;

while(!kolejka.empty())
{
int u = kolejka.back();
kolejka.pop_back();
if(kolor[u]) ++red;
else ++blue;
next = (kolor[u]+1)&1;
//printf("%d ",u);
for(int j=0;j<gr[u].size();j++)
{
if(!v[gr[u][j]])
{
v[gr[u][j]] = true;
kolor [ gr[u][j] ] = next;
kolejka.push_back(gr[u][j]);
}
else
if (kolor[u] == kolor[gr[u][j]])
ok = true;
}

}
if(ok) return 0;
return max(red,blue);

}

int main()
{
scanf("%d",&m);
while(m--)
{
clear();
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a);
while(a--)
{
scanf("%d",&b);
gr[b].push_back(i);
gr[i].push_back(b);
}
}
/*
pisz();
*/
for(int i=1;i<=n;i++)
if(!v[i])
wynik+=bfs(i);

printf("%d\n",wynik);
//if(m)puts("");
//       for(int i=1;i<=n;i++)
//        printf("%d ",kolor[i]);
//    puts("");

}
}
``````

Scarecrow
Learning poster
Posts: 69
Joined: Wed Oct 19, 2011 9:06 pm

### Re: 10505 - Montesco vs Capuleto

AC

Code: Select all

``````AC
``````
Last edited by Scarecrow on Fri Jul 27, 2012 2:18 pm, edited 1 time in total.
Do or do not. There is no try.

Scarecrow
Learning poster
Posts: 69
Joined: Wed Oct 19, 2011 9:06 pm

### Re: 10505 - Montesco vs Capuleto

some input sets are like this. be sure to handle these

Code: Select all

``````1

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

Code: Select all

``3``
Do or do not. There is no try.

Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm

### Re: 10505 - Montesco vs Capuleto

cutt>>>>>>>>>>>>>AC
we r surrounded by happiness
need eyes to feel it!

m.shawkey
New poster
Posts: 9
Joined: Tue Jun 11, 2013 2:58 pm

### Re: 10505 - Montesco vs Capuleto

my code works fine for all test cases posted here, but it gives wrong answer, can any one help me, please?

my code here http://ideone.com/hHaf3N