15. Красно-синий граф

Задача

Для полного ориентированного графа на $n$ вершинах рёбра раскрашены в красный и синий цвет. Проверьте, существует ли пара вершин $(v, u)$, между которыми есть и красный, и синий путь.

Входные данные

В первой строке задано число $n$ ($1 \leqslant n \leqslant 5000$). Далее следует описание графа: $i$-я строка содержит $n-i$ символов R или B, где $j$-й символ задаёт цвет ребра $i \to (i+j)$.

Выходные данные

Выведите YES, если существует пара $(v, u)$, для которой можно построить красный и синий путь от $v$ к $u$. Иначе выведите NO.

Примеры

стандартный ввод      стандартный вывод
3                      YES
RB
R

3                      NO
RR
R

Ограничения

  • Время: 1 секунда
  • Память: 256 мегабайт
Редакционный разбор Направление всех рёбер фиксировано: из меньшего номера в больший. Значит, графы по отдельным цветам — DAG’и. Путь из $v$ в $u$ возможен только если $v < u$, поэтому достаточно проверить пары с таким порядком. Для ускорения используем битсеты. Пусть `red[i]` и `blue[i]` — битовые маски достижимых вершин из $i$ по красным/синим рёбрам. Заполним их динамикой «сверху вниз»: обходим вершины в порядке убывания, инициализируем `mask` нулями. Для каждого ребра $i \to j$ соответствующего цвета объединяем маску `red[i] |= red[j]; red[i].set(j);`. Аналогично для синего цвета. После заполнения достаточно пройти по всем $i < j$ и проверить, есть ли `red[i][j] && blue[i][j]`. При $n = 5000$ битсеты длины $n$ умещаются в ~80 64-битных слов, что даёт сложность порядка $O(n^2 / 64)$ — приемлемо. Если условие выполняется хотя бы для одной пары, отвечаем «YES», иначе «NO».

Mentioned by