## 10505 - Montesco vs Capuleto

Moderator: Board moderators

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..
helloneo
Guru

Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

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?
yiuyuho
A great helper

Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States

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
`2103 2 3 41 601 501 93 8 9 1001 30203 2 3 4000`

Output
Code: Select all
`019`

Thanks
Young20
New poster

Posts: 5
Joined: Fri Jul 06, 2007 6:39 pm

My AC code gives the same output..
helloneo
Guru

Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

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   220typedef 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.
Young20
New poster

Posts: 5
Joined: Fri Jul 06, 2007 6:39 pm

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?
yiuyuho
A great helper

Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States

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[b][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[b][1] is 0 that means b has same color with its parent. if bipartite[b][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
`11002 23003 3 8 113 8 11 131 111 132 4 52 18 133 20 18 213 4 5 6 1 2100001 212 9 101 2104 12 17 19 25002 25 274 21 22 23 2402 24 2603 30 37 383 26 28 290000001 292 29 311 403 31 39 510000000000002 58 59001 792 51 522 53 521 53000000000001 5301 7901 530001 53 54 55 56 70 72 7300003 73 74 7603 76 77 832 90 1001 8303 83 85 870000000002 87 89`

my output like that
Code: Select all
`73`

Am I right?
Young20
New poster

Posts: 5
Joined: Fri Jul 06, 2007 6:39 pm

yiuyuho
A great helper

Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States

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
shakil
Learning poster

Posts: 74
Joined: Sat Jul 15, 2006 6:28 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("");    }}`
withelm
New poster

Posts: 1
Joined: Sat Dec 24, 2011 1:52 am

### 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
`155 2 4 6 8 103 1 3 6003 1 6 7`

output

Code: Select all
`3`
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

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