Can anyone who solved this problem explain how to solve subtask 2 and full solution please ? https://oj.uz/problem/view/BOI17_catinatree
→ Обратите внимание
До соревнования
Rayan Programming Contest 2024 - Selection (Codeforces Round 989, Div. 1 + Div. 2)
16:49:24
Зарегистрироваться »
Rayan Programming Contest 2024 - Selection (Codeforces Round 989, Div. 1 + Div. 2)
16:49:24
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 155 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 10 | djm03178 | 152 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 30.11.2024 00:45:36 (k1).
Десктопная версия, переключиться на мобильную.
При поддержке
Auto comment: topic has been updated by youssefbou62 (previous revision, new revision, compare).
Same problem with weights on nodes : Link
Here's the O(n) solution described as well as the subtasks : Link
keep taking the deepest node.Invalidate all nodes with with distance <=d from that node.
centroid decomposition
for each node in the centroid tree keep all the nodes in its subtree in sorted order by distance from it in ascending order
when invalidating a node check check it and all of its parents in the centroid tree and start invalidating from the first node not already invalidated if the distance<=d.keep increasing the counter
https://oj.uz/submission/244589 O(n*logn*logn)