| 1 Казадаев Максим Сергеевич, 18 августа 2020 г. 20:35:28 |
| К комментарию ниже: Можно идти по двум цепочкам предков с конца и при первом несовпадении вывести предка. Будет то же самое, но гораздо быстрее. (нужно еще рассмотреть крайние случаи, когда одна из цепочек закончится)
|
|
|
| 2 Кудрин Максим Витальевич, 13 июля 2020 г. 8:18:23 |
| Удивлен, что не выдало Тайм Лимита. Просто записал всех предков одного отдела, потом пошёл по предкам второго отдела (начиная с него же), и каждого предка проверял в предках первого отдела. Первое совпадение на экран. По идее так много раз перебирать, должен тайм лимит быть, но к моему счастью AС
|
|
|
| 3 Чопонов Данияр, 22 марта 2020 г. 0:01:55 |
| предподсчет зад O(n) и lca за O(log n)
|
|
|
| 4 Вязовцев Андрей Викторович, 25 марта 2019 г. 18:06:17 |
| Если подумать, то задача очень лёгкая. Всего лишь ввод данных и цикл while с телом в 2 строчки, после чего уже вывод.
|
|
|
| 5 Зыков Алексей Александрович, 03 февраля 2018 г. 10:57:47 |
| O(N)
|
|
|
| 6 Линар Хилажев, 14 июля 2017 г. 13:02:01 |
| Решал дфсом, искал вершину с которое соединены оба отдела.
|
|
|
| 7 Нуриев Наиль Дамирович, 19 июня 2015 г. 20:36:54 |
| O(n + m)
|
|
|
| 8 Асхат, 18 октября 2014 г. 17:30:44 |
| dfs)
|
|
|
| 9 Павлов Михаил Валерьевич, 04 марта 2014 г. 17:40:22 |
| и тут до меня дошло что решение то БЕЗ всяких DFS и прочей фигни которую я так старательно отлаживаю вот уже второй день. ИТОГ : 5 минут и AC с первого раза.
|
|
|
| 10 Филипп Кофман Олегович, 11 сентября 2013 г. 1:42:58 |
| Оу. Думал LCA. прочитал и понял все что есть на emax-x. Стало страшно)) Посмотрел на сложность всего 40%. Понял что простая на самом деле. И здал решение за O( logN ) без предпрощетов бинарных подьёмов и так далее =) Советую просто порисовать деревья и потыкать пары вершин)
|
|
|
| 11 Бабанов Айдар Нурланович, 06 марта 2012 г. 17:48:12 |
А если нету ответа?
Ответ всегда есть.
|
|
|
| 12 Бабанов Айдар Нурланович, 06 марта 2012 г. 12:13:25 |
А теперь-то уже полиция))
И что, теперь мне все задачи про милицию переименовывать? :)
|
|
|
| 13 Балакший Андрей Владимирович, 11 ноября 2011 г. 23:54:54 |
| Мда, метод двоичного подъёма оказался намного элементарнее, да и предподсчет O(NlogN) и поиск lca за O(logN) очень симпатичен...
|
|
|
| 14 Балакший Андрей Владимирович, 26 октября 2011 г. 23:02:56 |
| точнее за искать за O(logN) + начальный предподсчет за O(n)
|
|
|
| 15 Балакший Андрей Владимирович, 26 октября 2011 г. 23:02:09 |
| Уф, перемудрил с реализацией.... хотя если добавить дерево отрезков, то можно будет искать lca заданных вершин за O(N + logN)
|
|
|
| 16 на на на, 30 июля 2011 г. 20:53:11 |
| задача просто на LCA(наименьший общий предок)
|
|
|
| 17 Егор, 14 июня 2011 г. 12:44:49 |
| С какой темой из теории графов связано решение данной задачи,
|
|
|
| 18 Шуршилов Артём Александрович, 05 ноября 2010 г. 22:27:49 |
10
8 7
1 2 3 1 1 3 4 5 6
Ответ: 3
|
|
|
| 19 Ivan Dvitriev Vaslylev, 07 апреля 2010 г. 23:14:12 |
>5
>2 4
>1 2 3 4
и 2 тест
>7
>2 3
>1 2 2 4 5 1
моё AC решение выдает в обоих тестах - 2.
|
|
|
| 20 Коншин Андрей Сергеевич, 09 января 2010 г. 15:11:34 |
Я вот не понимаю....через 1-ый отдел можно просмотреть все другие отделы,а через любой другой только те,с которыми этот отдел соединен???
И кто нить скажите,что будет при этих 2ух тестах
5
2 4
1 2 3 4
и 2 тест
7
2 3
1 2 2 4 5 1
|
|
|
