vatsal's blog

Help on 131D
By vatsal, history, 8 years ago, In English

Here is my sumbission on problem. I am getting WA on test8.What I do is I find all the incycle vertics and put them into set and then update the distances from it. Can anyone please point out the mistake in my code?

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

»
8 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

I haven't seen your code but there is an easier way. Just start processing from the leaves (nodes with degree 1). When you remove all such nodes, you get another set of leaves. Repeat this process. When you don't have any leaf remaining, that means only cycle vertices are left. Assign 0 to all of them and process the deleted nodes in reverse order of their deletion.

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

    There maybe many approaches to a single problem. I would like to know why is this particular approach wrong despite of its straightforwardness. Can you please help? Even I need help in this problem...My approach is similar to the one mentioned by vatsal :/

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      This approach is not wrong. I used the same in my submission 12890890 to get AC.

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

        Yes I got it...actually I assumed that node 1 is always in the cycle. Thank you for helping though :)

        → Reply