--->
16 задач
<---
Источники
Фермер Архип решил заняться земледелием и выращивать брюссельскую редиску. Для этого он купил прямоугольное поле, состоящее из \(n\) рядов по \(m\) участков в каждом. Все участки являются одинаковыми и имеют квадратную форму. Оказалось, что на момент покупки некоторые из этих участков уже удобрены, а некоторые — нет. Редиска растет только на удобренных участках.
Для получения большего урожая Архип решил удобрить некоторый прямоугольный фрагмент поля, состоящий из целых участков. В выбранном фрагменте Архип удобряет каждый участок. Повторное удобрение участка делает его непригодным к выращиванию брюссельской редиски. Закончив удобрять, фермер выбирает для посадки редиски прямоугольный фрагмент поля, состоящий из целых участков, каждый из которых удобрен ровно один раз.
Архип должен выбрать на поле фрагмент для удобрения таким образом, чтобы фрагмент для посадки редиски имел максимальную площадь.
Напишите программу, которая по заданному полю находит фрагмент поля для удобрения и фрагмент поля под посадку.
В первой строке входного файла записаны натуральные числа \(n\) и \(m\) (\(2\le n\le2\,000\), \(2\le m\le2\,000\)), где \(n\) — количество рядов на поле, а \(m\) — количество участков в каждом ряду (количество столбцов). Далее в \(n\) строках содержится описание поля. Каждая из этих \(n\) строк содержит \(m\) символов. Символ «1» обозначает, что соответствующий участок поля удобрен, а «0» — не удобрен. Гарантируется, что поле содержит хотя бы один удобренный и хотя бы один неудобренный участок. Поле расположено таким образом, что первая строка его описания соответствует северной стороне, а первый столбец — западной стороне.
Первая строка должна описывать фрагмент поля для удобрения. Фрагмент описывается четырьмя числами \(a\), \(b\), \(c\), \(d\), где \(a\) и \(b\) — номер ряда и столбца самого северо-западного его участка, а \(c\) и \(d\) — номер ряда и столбца самого юго-восточного. Ряды нумеруются с севера на юг от 1 до \(n\), а столбцы — с запада на восток от 1 до \(m\).
Вторая строка должна описывать фрагмент под посадку в том же формате.
Третья строка должна содержать площадь фрагмента (количество участков) под посадку.
Если решений несколько, выведите любое.
Система оценивания
Решения, корректно работающие при \(n\le40\) и \(m\le40\), будут оцениваться из 30 баллов, а решения, корректно работающие при \(n\le300\) и \(m\le300\), будут оцениваться из 60 баллов.
4 4 1110 1010 1110 0000
2 2 2 2 1 1 3 3 9
Дан неориентированный граф. Над ним в заданном порядке производят операции следующих двух типов:
cut — разрезать граф, то есть удалить из него ребро;
ask — проверить, лежат ли две вершины графа
в одной компоненте связности.
Известно, что после выполнения всех операций типа cut рёбер в графе
не осталось. Найдите результат выполнения каждой из операций типа ask.
Первая строка входного файла содержит три целых числа, разделённые пробелами — количество вершин графа \(n\), количество рёбер \(m\) и количество операций \(k\) (\(1 \le n \le 50\,000\), \(0 \le m \le 100\,000\), \(m \le k \le 150\,000\)).
Следующие \(m\) строк задают рёбра графа; \(i\)-ая из этих строк содержит два числа \(u_i\) и \(v_i\) (\(1 \le u_i, \, v_i \le n\)), разделённые пробелами — номера концов \(i\)-го ребра. Вершины нумеруются с единицы; граф не содержит петель и кратных рёбер.
Далее следуют \(k\) строк, описывающих операции. Операция типа cut
задаётся строкой „cut \(u\) \(v\)“ (\(1 \le u, \, v \le n\)),
которая означает, что из графа удаляют ребро между вершинами \(u\) и \(v\).
Операция типа ask задаётся строкой „ask \(u\) \(v\)“
(\(1 \le u, \, v \le n\)), которая означает, что необходимо
узнать, лежат ли в данный момент вершины \(u\) и \(v\) в одной компоненте
связности. Гарантируется, что каждое ребро графа встретится
в операциях типа cut ровно один раз.
Для каждой операции ask во входном файле выведите на отдельной строке
слово „YES“, если две указанные вершины лежат в одной компоненте
связности, и „NO“ в противном случае. Порядок ответов должен
соответствовать порядку операций ask во входном файле.
3 3 7 1 2 2 3 3 1 ask 3 3 cut 1 2 ask 1 2 cut 1 3 ask 2 1 cut 2 3 ask 3 1
YES YES NO NO
Изначально имеется дерево состоящее только из корня (вершина с номером \(1\)). Требуется научиться отвечать на следующие запросы:
Все номера вершин от \(1\) до \(N\).
В каждый момент времени у нас есть одно дерево.
В первой строке входного файла содержится число \(k\) — количество запросов. Следующие \(k\) строк содержат сами запросы. Гарантируется, что число запросов каждого из типов не превосходит \(500\,000\).
Для каждого запроса типа GET выведите в отдельную строку одно целое число — ответ на соответствующий запрос.
9 ADD 1 2 ADD 1 3 ADD 2 4 GET 1 3 GET 2 3 GET 3 4 ADD 2 5 GET 4 5 GET 5 5
1 1 1 2 5
Напишите программу, которая будет содержать реализацию структуры данных для совокупности непересекающихся подмножеств (disjoint sets) и обрабатывать запросы таких видов:
RESET n — создать новую серию подмножеств: множество из одного только элемента 0, из одного только элемента 1, и так до множества из одного только элемента n–1 включительно. Если структура уже содержала какую-то другую совокупность непересекающихся подмножеств, вся соответствующая информация утрачивается. На стандартный выход (экран) при этом следует вывести два слова через пробел «RESET DONE».
JOIN j k — объединить подмножества, которым принадлежат элемент j и элемент k. Если элементы и так принадлежали одному подмножеству, вывести на стандартный выход (экран) слово «ALREADY», после него через пробелы те же числа j и k в том же порядке. Если элементы до сих пор принадлежали разным подмножествам, то действие происходит только с данными в памяти, на экран ничего не выводится.
CHECK j k — проверить, одному ли подмножеству принадлежат элемент j и элемент k; вывести на стандартный выход (экран) слово «YES» (если одному) или слово «NO» (если разным).
Во входных данных содержится последовательность запросов RESET, JOIN и CHECK — каждый в отдельной строке, согласно вышеописанному формату. Гарантированно, что первая строка содержит запрос RESET, а общее количество запросов RESET не превышает 5. Общее количество всех запросов не превышает 200000. Значение n в каждом запросе RESET не превышает 100000. В каждом запросе JOIN и в каждом запросе CHECK оба числа будут в диапазоне от 0 до n–1, где n — параметр последнего выполненного запроса RESET.
Для запросов RESET, CHECK и тех запросов JOIN, где элементы и так принадлежат одному подмножеству, выводить на стандартный выход (экран) соответствующий результат (в отдельной строке).
Ответы «NO» даются на запросы «CHECK 2 11» и «CHECK 9 1», ответ «ALREADY 4 1» — на второй из запросов «JOIN 4 1» (10-я строка), «YES» — на «CHECK 5 10».
RESET 15 JOIN 14 10 JOIN 13 8 JOIN 0 9 JOIN 8 3 JOIN 4 1 JOIN 10 5 JOIN 8 4 CHECK 2 11 JOIN 4 1 JOIN 2 6 CHECK 9 1 JOIN 6 5 CHECK 10 5
RESET DONE NO ALREADY 4 1 NO YES
Между пунктами с номерами 1, 2, ... , N(N ≤ 1500) проложено несколько дорог. Длина каждой дороги известна. По этой системе дорог можно добраться из любого упомянутого пункта в любой другой. Автозаправки расположены только в пунктах. Требуется определить, какое максимальное расстояние без заправки должен быть в состоянии проезжать автомобиль, чтобы без проблем передвигаться между пунктами.
В первой строке входного файла находятся числа N и K (количество дорог). В следующих K строках указаны пары пунктов, связанных дорогами и расстояние между ними — целое число километров, не превышающее 10000.
В выходном файле должно оказаться одно число длина максимального пробега без дозаправки.
3 2 1 2 5 1 3 10
10