Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки


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

Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!

Красноярский краевой Дворец пионеров, (c)2006 - 2024, ИНН 246305493507, E-mail: admin@acmp.ru