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

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.

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 »

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 »

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.

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

frastated

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

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 »

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 »

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
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko »

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 »

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

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.

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 »

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)

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 »

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 »

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 »

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 »

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 »

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