Unable to understand where my submission is failing. It looks like a standard DSU question. WA on TC-14.
https://mirror.codeforces.com/contest/755/submission/80885849
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
26:28:39
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
26:28:39
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 22.11.2024 15:06:22 (i1).
Десктопная версия, переключиться на мобильную.
При поддержке
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://mirror.codeforces.com/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.