My solution:
Let's build graph. There are undirected edge between vertex A and B if and only between passengers A and B exist contradictions.
Let's color each compenent of graph in two color. Then let's add ALL vertexS with same color(with min count) from each component to answer.
Why i get WA?

P.S.: between passengers A and B exist contradictions if and only if A was in placeA but B was in placeB and detected A there.

Edited by author 21.10.2014 03:02

Edited by author 21.10.2014 03:47

Do you add only one vertex per component that has color with less vertices count than the other? If so, you should add all vertices from each component instead.
Also I'd recommend you to check what you do with isolated vertices.

"Do you add only one vertex per component that has color with less vertices count than the other? If so, you should add all vertices from each component instead."
Yes. My pure English. =) I add all verticeS.

"Also I'd recommend you to check what you do with isolated vertices."
If component consist from one isolated vertices than I add to answer no vertex. If graph consist only from isolated vertices (sample test 2) than I add to answer vertex #1.

After +100500 submit I get test #5:
==============
3
A  1   3
WC 1   3
WC 0
==============

I just go mad =)
My code:
http://ideone.com/a9EPDj

Edited by author 21.10.2014 18:05

Edited by author 21.10.2014 18:22

It's hard to say what's wrong in your code. But after fast looking at it I would start with checking a condition if two person's statements contradict each other. It may be slightly incorrect.

I found the reason for WA5. The problem is that when a person ***doesn't contradict***, the info still can influence the answer. Example:
3
A 1 2
B 1 1
A 1 1

So, your prog finds 1 contradicting pair 1-2 and may think the guy 1 is the bad one, but this gives you 2 bad guys in total (because the guy 3 says he saw the guy 1 in place A), so the only right answer is #2. The test can be fixed a bit to make guy 1 the only bad guy.

So, first check for your prog is the following 2 tests:
3
A 1 2
B 1 1
A 1 1
=> answer 1 2

3
A 1 2
B 1 1
B 1 2
=> answer 1 1

Sad!I was failed in the test 32...

It is a maximum independent set problem ( NP problem). Greedy or random gives wa14. Method of branches and borders gives TL6. Help to choose algo!!!