Ещё одна задача про деревья
Очень сложная
Ограничение по времени выполнения 1 секунда
Ограничение по использованию памяти 256 мегабайт
Есть граф из вершин. Изначально он пустой. Нужно обработать запросов:
добавить ребро из вершины в вершину , при этом вершины и находятся в разных деревьях и вершина является корнем какого-то дерева.
по двум вершинам и определить, лежат ли они в одном дереве.
Решение задачи
Реализуем СНМ с эвристикой сжатия путей:
int n, m, l[NMAX]; int calc_leader (int v) { if (l[v] != v) l[v] = calc_leader (l[v]); return l[v]; } int main() { scanf ("%d%d", &n, &m); for (int i = 1; i <= n; i ++) l[i] = i; for (int i = 1; i <= m; i ++) { int x, y, z; scanf ("%d%d%d", &z, &x, &y); if (z == 1) l[y] = x; else if (calc_leader (x) == calc_leader (y)) printf ("YES\n"); else printf ("NO\n"); } }
Вам же предстоит сделать тест, на котором это решение будет работать долго. Более точно, нужно сделать тест, на котором количество вызовов функции calc_leader
будет не меньше, чем .
Входные данные
Входной файл содержит два целых числа и (, , ).
Выходные данные
Выведите строк. -ая строка должна иметь вид , если -ый запрос заключается в добавлении ребра из вершины в вершину , или , если спрашивается, лежат ли вершины и в одном дереве.
Примеры
Ввод #1
Ответ #1
Отправки 321