| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 160 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | orz | 146 |
| 9 | pajenegod | 145 |
| 9 | SecondThread | 145 |
Решал Ашку с тренировки СПбГУ (здесь) и у меня постоянно МЛЕ на 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