Блог пользователя Radebush

Автор Radebush, история, 6 лет назад, По-английски

I recently spotted this problem of IOI 2018. I couldn't come up with a proper approach. Only thing that I know is the solution is associated with graph. Can you please help me to solve this problem?

https://ioi2018.jp/wp-content/tasks/contest1/werewolf.pdf

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

You can find the solution here

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
  1. Create a new directed graph having 2*n nodes.
  2. The first n nodes are marked as H1, H2, ...., Hn and last n are marked as W1, W2, ..., Wn.
  3. For two node Hu and Hv, connect it if there is a edge between u and v and can be visited in human form. Similar things goes for Wu and Wv.
  4. Add a edge between every Hu and Wu.
  5. Run DFS(Hsoruce) and see if you can reach Wdestination.

The best part is you don't create the above graph explicitly. You calculate the graph on the fly form the original one. And most graph algorithm actually uses another implicit graph which is calculated on the fly (yes, Dijkstra too).