Всем привет! Собственно вот задачка, подкиньте, пожалуйста, идею.
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
3 дня
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
3 дня
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 2 | maomao90 | 163 |
| 4 | atcoder_official | 161 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | nor | 153 |
| 9 | Dominater069 | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 20.11.2024 18:19:32 (g1).
Десктопная версия, переключиться на мобильную.
При поддержке
LCA
Спасибо. Не изучал еще такого алгоритма.
Omelianenko прав.
LCA ищет наименьшего общего предка двух вершин. Топологическа сортировка для его постоения нужна (если это не Тарьян). В данной задаче ответ на запрос 1, только если вершины лежат в одной компоненте связности и LCA(a,b)=a, во всех других случаях ответ 0.
За чушь собачью написаную мной в комменте ниже дико извиняюсь это была попытка решить задачу не думая.
надо воспользоваться такой штукой "время входа-выхода в dfs". так как нам дан связный граф без циклов (деревце), то истинность данного условия (tin[u] < tin[v] && tout[u] > tout[v]) равносильна тому, что u предок v. вы слышали что-нибудь об этом, знаете, как считать tin[] и tout[]?
Да, слышал. Спасибо, сейчас подумаю над вашей мыслью.
Простой способ. Топологическая сортировка.
Запускаем dfs из корней деревьев. Запоминаем время выхода из каждой вершины. У кого время больше, тот и предок. Не забудьте покрасить вершины номерами компоненты связности в которых они лежат, а то могут сравниваться вершины с разных компонент, очевидно, что для них ответ 0.
Может я неверно Вас понял, но у в тесте, который в сэмпле по этому алгоритму будет неверный ответ для 6 5. Т.к из 5-ти мы можем выйти раньше, чем 6-ти.
очевидно, что это не работает.
Задача с qbit.org.ua Авторское решение предполагает топологическую сортировку графа.