10505 - Montesco vs Capuleto

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

Moderator: Board moderators

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

Post by helloneo » Fri Dec 22, 2006 6:46 am

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

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

Post by yiuyuho » Fri Dec 22, 2006 8:10 am

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? :-P

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

Post by Young20 » Fri Jul 06, 2007 6:52 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

Post by helloneo » Fri Jul 06, 2007 6:57 pm

My AC code gives the same output..

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

Post by Young20 » Fri Jul 06, 2007 8:41 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:

Post by yiuyuho » Fri Jul 06, 2007 9:40 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?

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

Post by Young20 » Sat Jul 07, 2007 2:41 am

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
New poster
Posts: 5
Joined: Fri Jul 06, 2007 6:39 pm

Post by Young20 » Sat Jul 07, 2007 4:23 pm

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
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Post by yiuyuho » Sat Jul 07, 2007 9:17 pm

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

shakil
Learning poster
Posts: 74
Joined: Sat Jul 15, 2006 6:28 am
Location: CUET , bangladesh
Contact:

Post by shakil » Fri Aug 03, 2007 10:44 am

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

Post by withelm » Sat Dec 24, 2011 1:55 am

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

Post by Scarecrow » Thu Jul 19, 2012 8:09 pm

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

Post by Scarecrow » Tue Jul 24, 2012 2:40 pm

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.

User avatar
mahade hasan
Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm
Location: University of Rajshahi,Bangladesh

Re: 10505 - Montesco vs Capuleto

Post by mahade hasan » Sat Jan 19, 2013 7:23 pm

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

Post by m.shawkey » Tue Jul 30, 2013 7:30 pm

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

Post Reply

Return to “Volume 105 (10500-10599)”