10505 - Montesco vs Capuleto

[Shuvra(CSE-BUET)]

Hi .I read the previous posts and now very upset as I tried all inputs posted and got the right answer. Now would you please check my code and say what is wrong there?
.....................................................................................................................................................................................................................
#include <stdio.h>
struct a{

int col,bi,c,data;

}p[205][205];//c for component number ,col for coloring ,bi for bicoloring,data for is there a edge
int v,maxi,elem,comp;
void visit(int u ){
int i;
p.col=1;
p.c=comp;
if(elem!=-1)
++elem;//elem for number of elements in a component return -1 if bicoloring not possible for that component
for(i=1;i<=v;i++)
{
if( p.data==1 && p.col==0 )
{
p.bi =1-p.bi;

visit(i);
}
else if( p.c== p.c && p.col==1 && p.data==1 && p[i][i].bi == p[u][u].bi)
{
elem=-1;

}
}
p[u][u].col=2;

}

void dfs(){
int i;
maxi=0;
comp=0;
for(i=1;i<=v;i++)
{
p[i][i].col=0;
p[i][i].c=-1;
p[i][i].bi=-1;
}
for(i=1;i<=v;i++)
{
elem=0;
if(p[i][i].col==0)
{
p[i][i].bi=0;
++comp;
visit(i);
if(elem!=-1)
{
if(elem%2==0)
maxi=maxi+elem/2;
else
maxi =maxi + elem/2+1;

}//if

}//if
}//for

}




void main(){
long int test;
int x,y,n,i,j;
scanf("%ld\n",&test);
while(test-->0){
scanf("%d",&n);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++){
p[i][j].data=0;

}
v=n;
for(i=1;i<=n;i++){

scanf("%d",&x);
while(x-->0)
{
scanf("%d",&y);
if(y>n)
continue;
p[i][y].data=1;
p[y][i].data=1;
}

}
dfs();

if(test>1)
printf("%d\n",maxi);
else
printf("%d",maxi);


}

}

[Martin Macko]

There is already a thread on this problem. If there is a thread on a particular problem, please, use it to post your question and do not create a new one. (see http://online-judge.uva.es/board/viewto ... ight=10505)

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

[daveon]

There is already a thread on this problem. If there is a thread on a particular problem, please, use it to post your question and do not create a new one. (see http://online-judge.uva.es/board/viewto ... ight=10505)

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

Perhaps the enforcement measures should be stronger rather than telling users not to start a new post.

[Kallol]

Hey !
i am totally fade up with htis problem. I left no stone unturned but invain. My code passes all the sample cases given in this forum but for an unknows reason judge giving it a WA !!
here is my code:

Code: Select all

#include<stdio.h>
#include<memory.h>

#define WHITE 0
#define GREY 1
#define BLACK 2
#define RED 4
#define GREEN 5
#define INF 32700

class node
{
public:
	int col;
	int d;
	int f;
	int BC;
	bool isPedant;
};

bool a[205][205];
node N[205];
int T;
int n;
bool flag;
void init(int n)
{
	int i;
	for(i=1;i<=n;i++)
	{
		N[i].col=WHITE;
		N[i].d=INF;
		N[i].f=INF;
		N[i].BC=WHITE;
		N[i].isPedant=false;
	}
}

int oposit_col(int color)
{
	if(color==RED)
	{
		return GREEN;
	}
	return RED;
}

void visit(int node,int color)
{
	T++;
	N[node].d=T;
	N[node].col=GREY;
	N[node].BC=color;
	int i;
	for(i=1;i<=n;i++)
	{
		if(a[node][i] && N[i].col==WHITE)
		{
			visit(i,oposit_col(color));
		}
		else if(a[node][i] && N[i].BC==color)
		{
			flag=true;
			//return;
		}
	}
	T++;
	N[node].col=BLACK;
	N[node].f=T;
}

int main(void)
{
	int test,t,e,i,j;
	scanf("%d",&test);
	while(test--)
	{
		scanf("%d",&n);
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=n;j++)
			{
				a[i][j]=false;
			}
		}
		init(n);
		for(i=1;i<=n;i++)
		{
			scanf("%d",&t);
			for(j=0;j<t;j++)
			{
				scanf("%d",&e);
				a[i][e]=true;
				a[e][i]=true;
			}
		}
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=n;j++)
			{
				if(a[i][j])
				{
					break;
				}
			}
			if(j>n)
			{
				N[i].isPedant=true;
			}
		}
		T=0;
		flag=false;
		int stime,ftime;
		int countr=0;
		int countg=0;
		for(i=1;i<=n;i++)
		{
			if(N[i].col==WHITE && !N[i].isPedant)
			{
				flag=false;
				stime=T;
				visit(i,RED);
				ftime=T;

				if(!flag)
				{
					for(j=1;j<=n;j++)
					{
						if(N[j].d>stime && N[j].f<=ftime)
						{
							if(N[j].BC==RED)
							{
								countr++;
							}
							else if(N[j].BC==GREEN)
							{
								countg++;
							}
						}
					}
				}
			}
		}

		int white=0;
		int count=0;;

		for(i=1;i<=n;i++)
		{
			if(N[i].col==WHITE)
			{
				white++;
			}
		}
		count=countr>countg?countr:countg;
		count+=white;
		printf("%d\n",count);
	
	}
	return 0;
}

[Martin Macko]

Perhaps the enforcement measures should be stronger rather than telling users not to start a new post.

If you have an idea how to do it, we could suggest it to admins.

[daveon]

Well, the simplest idea is to let the admins create a thread for each problem. Which means that users are not allowed to start a new thread in the forums: VOLUME1-VOLUMEN.

[Martin Macko]

Well, the simplest idea is to let the admins create a thread for each problem. Which means that users are not allowed to start a new thread in the forums: VOLUME1-VOLUMEN.

Good idea

We could try to ask admins to do it. Let's post it as a suggestion to Bugs and suggestions forum. We'll see what's admins opinion on this problem.

[daveon]

I'm sure the admins have already considered this. And plus, having extra threads doesn't bother me.

[Shuvra(CSE-BUET)]

I am a new poster and all that I can say that my inexperience caused this problem. I shall try to avoid posting same topic in a new thread next time.

[Martin Macko]

Hi .I read the previous posts and now very upset as I tried all inputs posted and got the right answer. Now would you please check my code and say what is wrong there?

Firstly: Why don't you write '\n' after the last two numbers?

• if(test>1)
  • printf("%d\n",maxi);
  else
  • printf("%d",maxi);

Secondly: Your program doesn't work for:

Code: Select all

1

4
3 2 3 4
1 1
1 1
1 1

The correct output is:

Code: Select all

3

Thirdly: In the future, please, use the [code] ... [/code] tags (or anything else that woud do something similar) around your code to make it indentated, so it's more readable. (see http://online-judge.uva.es/board/faq.php?mode=bbcode)

[Martin Macko]

Hey !
i am totally fade up with htis problem. I left no stone unturned but invain. My code passes all the sample cases given in this forum but for an unknows reason judge giving it a WA !!
here is my code:

Your program doesn't work for:

Code: Select all

1

6
2 3 4
1 5
1 1
1 1
2 2 6
1

The correct output:

Code: Select all

4

[asif_rahman0]

Is the following output correct?
Input:

Code: Select all

5

7
2 2 3
1 1
3 1 7 4
2 7 3
0
0
2 3 4


7
2 2 3
0
0
2 5 7
0
1 7
0

10
2 2 3
0
0
2 5 7
0
1 7
0
0
0
2 8 9

20
2 2 3
2 5 3
1 9
0
1 4
3 9 7 8
1 8
0
1 10
0
2 13 12
2 13 15
1 17
0
0
0
0
2 20 19
1 20
0


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

Output:

Code: Select all

3
4
6
6
2

bye
rabbi

[Erik]

Hi,

my accepted program outputs

Code: Select all

2
4
6
2
0

Cu, Erik

[Erik]

Hi,

In all testcases you have wrong there are non-bipartite graphs.
So obviously you handle these the wrong way.

Cu, Erik

[yiuyuho]

Hmm...I am quite confused, the problem says:
- Anti-transitive. If a is an enemy of b, and b is an enemy of c, then a is a friend of c. Also, the enemies of the friends of a are his enemies, and the friends of the friends of a are his friends.

Doesn't that mean the components of the given graphs are all bipartite? But the test case 3 does not satisfy that...

In Sample case 3, 1 is the enemy of 2, 2 is the enemy of 3, then by the rule 1 is a friend of 3, but then there's an extra input saying that 1 and 3 are enemies..... So people can be enemy and friends at the same time?

I must be missing something, please tell me know!