Processing math: 100%

4-й этап Республиканской олимпиады по информатике 2020-2021, 2 тура


Задача C. Марафон Канто

Ограничение по времени:
2 секунды
Ограничение по памяти:
256 мегабайт

Скоро лето, Есмахан решил, что пора начать бегать по утрам в своем городе Канто. Город Канто представляет собой n перекрестков соединённых n1 дорогой, где от любого перекрестка можно добраться до любого другого перекрестка двигаясь по дорогам. В планах было начать бегать с воскресенья, однако в этот же день был назначен городской ежегодный веломарафон Канто. Определим маршрут (a,b), что a<b, множеством дорог, которые лежат на кратчайшем пути между стартовым перекрестком a и конечным перекрестком b. Длиной маршрута (a,b) будем называть количество дорог по которым он проходит. Есмахан не хочет бегать по занятым дорогам веломарафона во время пробежки. На вход дается n количество перекрёстков в городе Канто. Далее дается n1 дорога соединяющая два перекрестка. Гарантируется, что дается дороги таким образом, что от любого перекрестка можно добраться до любого другого перекрестка переходя только по дорогам. После дается q количество запросов на которые вы должны ответить. Запросы даются двух видов:
  1. x y, в нем вы должны ответить длиной самого длинного маршрута если веломарафон будет проходить через маршрут (x,y).
  2. k, в нем должны ответить количеством различных маршрутов (x,y), что Есмахан выберет маршрут длиной k.
Выведите ответ на каждый запрос. Поэтому хочет выяснить длину самого длинного маршрута (u,v) который будет проходить по свободным дорогам от веломарафона маршрутом (x,y), чтобы его пробежка была максимальна. Так же, Есмахан хочет выяснить сколько возможных маршрутов (x,y) веломарафона возможно, что его пробежке будет длины k?
Формат входного файла
Первая строка содержит одно целое число n (2<=n<=5105), обозначающее количество перекрестков в городе Канто. В каждой из следующих n1 строк содержится описание дорог: два целых числа u и v (1<=v,u<=n,uv). Следующая строка содержит одно целое число q (1<=q<=5105), обозначающее количество запросов. Следующие q строк содержат описания запросов. Каждый запрос задан в одном из следующих форматов в зависимости от типа запроса: 1 x y (1<=x<y<=n) для запросов первого типа. 2 k (0<=k<=n1) для запросов второго типа.
Формат выходного файла
Для каждого запроса выведите ответ на него.
Система оценки
Данная задача содержит 10 подзадач, в которых выполняются следующие ограничения:
  1. Примеры из условия. Оценивается в 0 баллов.
  2. n<=1000. Гарантируется, что ui=i, vi=i+1 для всех i (1<=i<n). Оценивается в 8 баллов.
  3. Гарантируется, что ui=i, vi=i+1 для всех i (1<=i<n). Оценивается в 10 баллов.
  4. n,q<=500. Оценивается в 9 баллов.
  5. n,q<=3000. Оценивается в 11 баллов.
  6. Гарантируется, что все запросы 1-типа и xi=1 для всех i (1<=i<=q). Оценивается в 12 баллов.
  7. Гарантируется, что все запросы 1-типа. Оценивается в 12 баллов.
  8. q<=10. Оценивается в 11 баллов.
  9. ui=i+1,vi=i+12 для всех i (1<=i<n). Оценивается в 10 баллов.
  10. Исходные условия задачи. Оценивается в 17 баллов.
Пример:
Вход
8
1 2
2 3
2 4
3 5
1 6
4 7
7 8
6
2 3
1 4 6
1 1 8
2 4
1 2 3
2 2
Ответ
4
2
2
6
5
12
Замечание
В первом запросе следущие четыре веломаршрута заставят Есмахана выбрать маршрут длины 3: (1, 3), (1, 5), (3, 6), (5, 6). Во втором запросе два самых длинных маршрутов длины 2: (2, 5) и (4, 8). В третьем запросе один самый длинный маршрут длины 2: (2, 5). В четвертом запросе следущие шесть веломаршрутов заставят Есмахана выбрать маршрут длины 4: (2, 4), (2, 7), (2, 8), (4, 7), (4, 8), (7, 8). В пятом запросе один самый длинный маршрут длинны 5: (6, 8). В шестом запросе ответ 12. ( Narkhan Kamzabek )
посмотреть в олимпиаде

Комментарий/решение: