OJ Board

Posted: **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);

}

}

Posted: **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.

Posted: **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.

Posted: **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;
}

Posted: **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.

Posted: **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.

Posted: **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

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.

Posted: **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.

Posted: **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.

Posted: **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

The correct output is:

Code: Select all

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)

Posted: **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

The correct output:

Code: Select all

Posted: **Thu Sep 07, 2006 12:14 pm**

Is the following output correct?
Input:

Code: Select all

Output:

Code: Select all

bye
rabbi

Posted: **Thu Sep 07, 2006 2:00 pm**

Hi,

my accepted program outputs

Code: Select all

Cu, Erik

Posted: **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

Posted: **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!

OJ Board

10505 - Montesco vs Capuleto

10505(Montesco vs Copuleto)WA is my enemy

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

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

frastated

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

I am so sorry to all

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

Re: frastated