ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1045. Funny Game

Some hint about this problem.
Posted by Y.Y.M. 13 Jun 2004 10:14
1. If we regard the start airport as the root,it is clear that the graph is a tree.
2. If start from all the leaf airport that from one airport could win, start from this airport suerly will lose. Otherwise,he could win.
3. We use a flag to record start from one airport will win or not.Just DFS to obtain all flag.
In this way,you could get AC in O(e).
Is there any better way to solve this problem?
I think the answer is yes.
So,could you write down your thought?
Re: Some hint about this problem.
Posted by begi 11 Jan 2015 11:03
 I didn't want to create new thread, so I will just revive this thread.

My idead was to use simple minimax algorithm:

boolean firstWins(node v)
  for every neighbour u of node v check secondWins(u)
     return true if for some u second loses
return false

boolean secondWins(node v)
  for every neighbour u of node v check firstWins(u)
     return true if for some u first loses
return false

Hope it will be helpful to someone.

Edited by author 11.01.2015 11:04