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

lucindo
New poster
Posts: 11
Joined: Thu Sep 05, 2002 2:35 am
Contact:

Post by lucindo » Mon Jul 14, 2003 4:34 pm

windows2k,

In your DFS code seems that you aren't marking all nodes in the non-bipartite components. Try without recurtion.
[]'s

Lucindo

zoho ho
New poster
Posts: 4
Joined: Tue Aug 13, 2002 10:11 pm

for windows2k

Post by zoho ho » Tue Jul 15, 2003 3:50 pm

try this

1

4
2 2 3
3 1 3 4
2 1 2
1 2

your answer is 1 , but the true answer is 0 ;

your DFS don,t mark node 4 and just return false ;

---------
huhuhu...
I have not ICQ or any online Messenger
If you want tell me any private you can
send mail to
u89156@ice.ntnu.edu.tw
thank you !

route
New poster
Posts: 39
Joined: Sat Dec 21, 2002 1:25 am

Re: for windows2k

Post by route » Sat Jul 19, 2003 1:33 pm

Hi, everybody,

What is the output of the followings ?

1

5
1 2
1 3
1 4
1 5
0

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Sat Jul 19, 2003 3:25 pm

Output should be 3.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Nick
Learning poster
Posts: 53
Joined: Sun Jan 12, 2003 4:49 am

DFS works just as fine

Post by Nick » Tue Jul 29, 2003 3:41 am

Hi, I use DFS on this problem and accepted just fine. I think its the coloring of the vertices that really matters, not the way you traverse the graph (for this kind of problems)

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Sun Oct 05, 2003 9:09 am

Anyone have any more test cases? I past all on this board, and still WA.

I basically use the algorithm everyone else described..
10

3
1 1
1 2
1 3

10
1 2
1 3
0
0
0
0
0
0
0
0

8
2 2 4
1 3
1 4
0
3 6 7 8
2 7 8
1 8
0

4
2 2 3
3 1 3 4
2 1 2
1 2


5
1 2
1 3
1 4
1 5
0

0

1
1 613

5
1 3
1 1
0
1 5
0

8
2 4 5
2 1 3
0
0
0
1 3
0
1 5

3
2 2 3
1 3
1 1
is what I used and I get:
3
9
2
0
3
0
1
3
5
0
Am I incorrect anywhere?

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Sun Oct 05, 2003 7:17 pm

The first test case should be 0, though I'm not sure there are any test cases like that in the input.

The rest of your output is correct.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Sun Oct 05, 2003 8:53 pm

I had it both ways and still WA.. any more inputs? :-?

hujialie
New poster
Posts: 43
Joined: Thu Apr 17, 2003 10:24 am
Location: Shanghai,China

Post by hujialie » Tue Oct 07, 2003 11:12 am

Hi,Larry.
Here are some tests where I found my mistake.
Hope it can help. :)

INPUT:
3

10
0
0
0
0
0
0
0
0
0
0

13
2 2 3
2 1 5
4 1 5 7 8
0
4 2 3 6 12
1 5
1 3
2 3 11
1 10
1 9
1 8
1 5
0

13
1 2
2 3 6
2 4 7
1 9
3 6 8 12
1 13
0
2 9 11
0
2 11 12
0
1 13
0

OUTPUT:
10
8
0
Retired from SJTU Accelerator 2004

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Tue Oct 07, 2003 8:31 pm

Passed all those.. =( I really hate to post my code and just ask people, but maybe I'll have to..

fpmc
New poster
Posts: 23
Joined: Tue Sep 30, 2003 11:44 pm

10505 Montesco vs Capuleto

Post by fpmc » Mon Oct 27, 2003 2:39 am

Hi, I'm kind of struggling with this problem.

It says that the 'enemy' relationship is anti-symmetric
ie. aRb and bRc -> not aRc

but in the sample input, we have
3
2 2 3
1 3
1 1
which is not anti-symmetric.

Can anyone give me some pointers in handling the case where it's not anti-symmetric? Do I ignore the anti-symmetric rule altogether?

Frank

GigS
New poster
Posts: 2
Joined: Sat Feb 08, 2003 2:34 am

Post by GigS » Fri Dec 19, 2003 1:00 am

There exsists test where number of enemy is bigger than N

for example

1

1 2

add a line
[i]if(a>n)continue; [/i]
in reading function should work (;
#gadu gadu 35622

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Thu Jan 15, 2004 2:02 am

I took that into account, as it was one of the test cases above. Still any more sample codes?

Fzaila
New poster
Posts: 1
Joined: Tue Mar 23, 2004 11:57 pm
Location: Pakistan

Post by Fzaila » Wed Mar 24, 2004 12:09 am

Can anybody tell me how i can get the input given by the Judge?

Becoz i am getting the WRONG ANSWER, although all of the sample inputs given in this forum + other inputs giving me the right answer. but judge is giving WRONG ANSWER .

Will somebody help me?

Thanks

Khaled_912
New poster
Posts: 33
Joined: Fri Jan 06, 2006 5:51 pm

Post by Khaled_912 » Tue Jul 04, 2006 9:44 pm

You must consider the graph as 'components', and count components that are not bipartite as 0.
Here is my DFS code:

Code: Select all

void dfs(int x, int c)
{
	if (v[x])  //visited
	{
		if (col[x] != c) bipartite = false; //color mismatch
		return;
	}
	v[x] = true;
	col[x] = c; //set the color
	//add the code for counting the node here

	int nc = inv(c); //the inverse of the color.. 0->1 and 1->0
	for (int i = 0 ; i < n ; i++)
		if (a[x][i]) dfs(i, nc);
}

Post Reply

Return to “Volume 105 (10500-10599)”