r3mark's blog

DMOJ New Year's 2019 Contest
By r3mark, history, 6 years ago, In English

Hello Codeforces!

You are invited to participate in a New Year's contest hosted on DMOJ. The contest begins at Jan 4, 2pm UTC, and will be open for a 36-hour period. The contest will have 8 problems written by Eliden and myself, and you will be given 4 hours to solve them. For further details, please visit the contest page.

Happy new year, and good luck!

UPD:

The round is over. Congratulations to the winners:

  1. ksun48
  2. Lewin
  3. LoneFox
  4. TLE
  5. kyleliu
  • Vote: I like it
  • +81
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by r3mark (previous revision, new revision, compare).

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C?

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

    Let dist(x) be the current distance from a1 to x. If adding the edge [ai, bi] reduces the value of dist(bi),  we push the pair {dist(bi), ai} to the corresponding vector for bi. After doing this for i = 1, 2, ..., n,  we can construct the answer by starting with bn and looking for the pair with first element dist(bn) in the vector for bn. The second element of this pair is the second to last node on the path. Letting this node equal p,  we can continue by searching for the pair with first element dist(bn) - 1 in the vector corresponding to p, and so on.

    Code

    → Reply