10505 - Montesco vs Capuleto

[helloneo]

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..
So, the answer is 0..

[yiuyuho]

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]

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]

My AC code gives the same output..

[Young20]

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

[yiuyuho]

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]

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.

Please help me out..

Thanks

[Young20]

Hmm..
How about this input..
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]

So, how does bipartite[x][1] help you with the calculation?

[shakil]

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);

}
}

[withelm]

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]

AC

Code: Select all

AC

[Scarecrow]

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

[mahade hasan]

cutt>>>>>>>>>>>>>AC

[m.shawkey]

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