Гран-прі Саратова - Codeforces

Гран-прі Саратова

може бути

Як розв’язати C і D?
Здається, я десь раніше бачив проблему J

  • fmota
  • 3 роки тому
  • 37

Як вирішити Е та Н? Вони обидва досить цікава проблема.

Перш за все, ми можемо запитати запити, щоб знайти всі листя дерева. Щоб перевірити, чи є вершина аркушем, ми задаємо запит, що містить все - 1 інші вершини; якщо відповідь така - 1, вершиною, яку ми виключили із запиту, є лист.

Тоді давайте вкорінюємо наше дерево на якомусь листку. Дозволяти L(х) - множина листків у піддереві вершини х . Оскільки вершин із ступенем 2 не існує, то для будь-яких двох вершин х і р L(х) ≠ L(р); крім того, х є родоначальником р iff. Тож якщо ми отримаємо інформацію про L(х) для кожної вершини, тоді ми можемо реконструювати дерево.

Для кореня, L(корінь) - сукупність усіх листків. На кожен другий лист z, L(z) = z>. Тож нам треба знайти L(х) лише для нелистяних. Щоб перевірити, чи є лист z знаходиться в піддереві нелистової вершини р, ми можемо задати запит 3 корінь р z .

Тож якщо кількість листків є л, ми повинні запитати (л - 1) ( - л) запити на пошук L(х) для всіх нелистових вершин. Це не перевищуватиме 2450, тому ми не будемо задавати більше 2550 запитів.

Класно! Це дійсно просте рішення.

У нас було рішення з однаковими запитами, але друга частина використовувала інший погляд.

Отже, для кожного листка ми знаємо «шлях» до кореня (лише вершини, а не їх порядок). Тепер перетин будь-яких двох таких "шляхів" - це також шлях до кореня з якоїсь вершини (їх lca). І кожна вершина - це lca з 2 аркушів (через відсутність 2-градусних вершин). Отже, зараз у нас є список "шляхів" для всіх вершин, і нам потрібно реконструювати дерево, що може бути зроблено простими dfs.

Якщо дерево є бамбуком, відповіді на всі запити першої частини алгоритму повинні бути - 1, чи не слід? Якщо ні, поясніть, чому.

E: У DAG кожен вузол може бути досягнутий за допомогою A і досягти B, тоді як

  • A не має ступеня
  • B не має перевищення ступеня
  • | ступінь | > = 1 і | ступінь | > = 1 для всіх вузлів, не A, B

Тепер слід вибрати два непересічні набори ребер EA, EB такі, що

  • краї в EA мають чіткі кінцеві точки
  • краї в EB мають чіткі вихідні точки

Це можна знайти за допомогою максимального збігу в О(мн 0,5)

Ого, потік для 1000000 країв, це новий запис, який я коли-небудь бачив:)

До речі це можна вирішити без потоку.

Я не розумію, чому це новий запис для вас, але двостороння відповідність на 10 ^ 6 вершин, очевидно, повинна працювати вчасно:)

Однак очищення графіку для кожного ТК було проблемою.

Крім того, це можна зробити за O (м), і навіть це можна зробити за мінімальних загальних витрат країв за O (м) час.

Додамо два ребра від B до A. Тепер у нас є лише умова на градуси. Отримаємо двосторонні grpah з 2 копіями вершин у лівій частині (що відповідає вершині в EA і вершині в EB) та ребрах у правій частині. Кожна вершина у другій частині матиме рівно два ребра (починати з EA та до і в EB). Проблема полягає в тому, щоб знайти ідеальне (за лівою частиною) узгодження на цьому графіку.