Clickbait's blog

8VC Venture Cup — PolandBall and Forest
By Clickbait, history, 4 years ago, In English

Unable to understand where my submission is failing. It looks like a standard DSU question. WA on TC-14.

https://codeforces.net/contest/755/submission/80885849

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

You have a bug in the union function, you should set parents of p1, p2 instead of x1, x2.

Also, this standard DSU question can be solved by counting a number of different values in the input sequence :)

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

    It doesn't work :(

    https://codeforces.net/contest/755/submission/80904257

    Did I rectify it correctly?

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

      Yes, the issue was a bit more subtle.

      You collect the answer by checking number of different values in parent array. However, because you use path compression algorithm, some of the values may not be up-to-date.

      You can either call find on all the nodes to solve this issue (this will update the values of parents for all nodes), or change the way in which you calculate the answer.

      → Reply