Benq's blog

CEOI 2008 Day 1 Information
By Benq, history, 5 years ago, In English

Does anyone have a $$$O(V^2)$$$ solution to this problem (available here)? The spoiler describes one but I don't understand what it means when it says to "search for this path backwards," and I can't find a model solution. (However, an $$$O(EV)$$$ solution with bitset did pass ...)

  • Vote: I like it
  • +50
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it -49 Vote: I do not like it

Send $5500 and I'll help!

→ Reply
»
5 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Not even one can answer Benq Question! Benqosity

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +39 Vote: I do not like it

I don't have an easy solution, but the following paper provide (somewhat sophisticated) $$$O(V^2)$$$ solutions:

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Thanks!

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    There is a simplified document for the second paper. It also claims to run in $$$O(kE \log V)$$$. Shoutout to rpeng. Link

    → Reply