Please read the new rule regarding the restriction on the use of AI tools. ×

et__fpme__'s blog

Difficulty interpreting question C. Restore Graph
By et__fpme__, history, 4 years ago, In English

Merry Christmas Everyone!

A problem from Div2 (237) C. Restore Graph asks to construct a graph when distances from a vertex are given.

The solutions and editorial to this problem indicate that we should be searching for nodes that are at dist[u] + 1 for a given node u and there should at least be one such node. But if we have distances = [0, 1, 4], then a tree like this 1-(1)->2-(3)->3 also satisfies the conditions in the question and there is no node at a distance of 2 from 1. Can anyone please help he understand what am I missing here?

Thanks in advance!

  • Vote: I like it
  • -18
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
4 years ago, # |
  Vote: I like it +14 Vote: I do not like it

The graph is unweighted my dude

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

    Ah damn missed a simple point!! Thanks Shisuko

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

      If it was weighted, then you could just make a star graph with the root as the center HAHAHA

      No worries though my dude, it happens to the best of us. Have fun solving :D

      → Reply