| № | Пользователь | Рейтинг |
|---|---|---|
| 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 | 156 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
Решал Ашку с тренировки СПбГУ (здесь) и у меня постоянно МЛЕ на 9-тесте. Подумал, что это из-за интов и заменил на шортЫ, теперь из интов только длины ребер. Но теперь у меня ТЛЕ. Прошу помочь решить эту задачу
Вот мой код с МЛЕ: https://pastebin.com/u8CkbhrE
Вот с ТЛЕ: https://pastebin.com/V8txT7KM
Алгоритм Краскала работает за $$$O(E\log{V})$$$. Алгоритм Прима (как и алгоритм Дейкстры) в варианте для плотных графов (без set или priority_queue) работает за $$$O(V^2)$$$.
В этой задаче $$$E \sim V^2$$$. Используя алгоритм Краскала, вы добавляете лишний логарифм. При $$$V = 5000$$$ решение со сложностью $$$V^2$$$ уложится в TL, со сложностью $$$V^2\log{V}$$$ — уже нет.
https://en.wikipedia.org/wiki/Euclidean_minimum_spanning_tree
А еще можно написать триангуляцию, написать O(NlogN) и вообще не смотреть на TL