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

Shuvra(CSE-BUET)
New poster
Posts: 19
Joined: Wed Jan 11, 2006 9:57 am
Location: Dhaka

10505(Montesco vs Copuleto)WA is my enemy

Post by Shuvra(CSE-BUET) » Tue Aug 15, 2006 7:08 am

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


}

}
Life is a challenge.

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: 10505(Montesco vs Copuleto)WA is my enemy

Post by Martin Macko » Tue Aug 15, 2006 11:46 am

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)
forum 'Volume CV' description wrote: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
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

Re: 10505(Montesco vs Copuleto)WA is my enemy

Post by daveon » Wed Aug 23, 2006 2:44 am

Martin Macko wrote: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)
forum 'Volume CV' description wrote: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.

User avatar
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

frastated

Post by Kallol » Wed Aug 23, 2006 7:49 pm

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;
}
Syed Ishtiaque Ahmed Kallol
CSE,BUET
Bangladesh

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: 10505(Montesco vs Copuleto)WA is my enemy

Post by Martin Macko » Wed Aug 23, 2006 8:57 pm

daveon wrote: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
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

Post by daveon » Thu Aug 24, 2006 1:58 am

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.

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » Thu Aug 24, 2006 5:58 am

daveon wrote: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 :wink:

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
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

Post by daveon » Fri Aug 25, 2006 1:34 am

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

Shuvra(CSE-BUET)
New poster
Posts: 19
Joined: Wed Jan 11, 2006 9:57 am
Location: Dhaka

I am so sorry to all

Post by Shuvra(CSE-BUET) » Thu Aug 31, 2006 1:54 pm

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.
Life is a challenge.

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: 10505(Montesco vs Copuleto)WA is my enemy

Post by Martin Macko » Fri Sep 01, 2006 12:26 pm

Shuvra(CSE-BUET) wrote: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?
Shuvra(CSE-BUET) wrote:
  • 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)

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: frastated

Post by Martin Macko » Fri Sep 01, 2006 12:54 pm

Kallol wrote: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
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

Post by asif_rahman0 » Thu Sep 07, 2006 12:14 pm

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
Learning poster
Posts: 67
Joined: Fri Jul 01, 2005 11:29 am
Location: Germany
Contact:

Post by Erik » Thu Sep 07, 2006 2:00 pm

Hi,

my accepted program outputs

Code: Select all

2
4
6
2
0
Cu, Erik :)

Erik
Learning poster
Posts: 67
Joined: Fri Jul 01, 2005 11:29 am
Location: Germany
Contact:

Post by Erik » Thu Sep 07, 2006 2:04 pm

Hi,

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

Cu, Erik :-)

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 4:47 am

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!

Post Reply

Return to “Volume 105 (10500-10599)”