Обсуждение @ 1198. Коррупция @ Timus Online Judge

Please, tell me the good idea of solving this problem, cuz at about four programs don't pass the 21st test...

Послано Alexey 9 июн 2006 11:55

subj

Re: Please, tell me the good idea of solving this problem, cuz at about four programs don't pass the 21st test...

Послано Samsonov Alex [USU] 9 июн 2006 12:28

Try to use cash.

Re: Please, tell me the good idea of solving this problem, cuz at about four programs don't pass the 21st test...

Послано Anton [SUrSU#6] 9 июн 2006 14:34

Why cash?
More explanations may be?

Re: Please, tell me the good idea of solving this problem, cuz at about four programs don't pass the 21st test...

Послано Vitalik 9 июн 2006 14:54

At me too a problem on 21 test.

Please, Help to solve this problem

Re: Please, tell me the good idea of solving this problem, cuz at about four programs don't pass the 21st test...

Послано Alexey 9 июн 2006 17:59

What do U mean "cash"? How to do it?
Will it be quicker?
Thanks.

Re: Please, tell me the good idea of solving this problem, cuz at about four programs don't pass the 21st test...

Послано shrek 23 ноя 2006 10:14

It's obviously a directed graph. We find its strongly-connected-components. Now if one of the vertices in one component satisfies the problem the other vertices in its component do. so we merge each component into one vertex. the remaining graph is a DAG (directed acyclic graph). the component which its in-degree is zero is the answer. and if there are more than one component with in-degree==zero then we have no answer because the graph is not connected.

Обсуждение задачи 1198. Коррупция