Unable to understand where my submission is failing. It looks like a standard DSU question. WA on TC-14.
Unable to understand where my submission is failing. It looks like a standard DSU question. WA on TC-14.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 155 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 145 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 132 |
| 10 | cry | 130 |
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 :)
It doesn't work :(
https://codeforces.me/contest/755/submission/80904257
Did I rectify it correctly?
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.