---> 16 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 1 2 3 4 >> Отображать по:
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Гора состоит из площадок, соединенных между собой узкими проходами. На каждой площадке лежит какое-то количество камней. У разных площадок разный рейтинг, зависящий от высоты площадки — чем выше площадка, тем больше ее рейтинг среди камней. Очевидно, что на площадках с более высоким рейтингом лежит большее количество камней.

В один солнечный день главный камень одной из площадок обратил внимание, что вокруг стало очень тесно. Но камни не могут катиться вверх, а на нижние площадки они катиться не хотят из-за плохого рейтинга. Поэтому главный камень пошел на хитрость. Он выбрал M камней и сказал каждому из них, что где-то внизу появилась замечательная площадка с самым высоким рейтингом на горе. Для полной правдоподобности он составил карту площадок, на которые можно скатиться с его площадки. Всего (включая переполненную площадку) оказалось N площадок. Поскольку главный камень ленивый, он не стал рисовать все пути между площадками, а просто нарисовал минимальное количество проходов между площадками, чтобы из его площадки можно было добраться в любую, находящуюся ниже. Он показал каждому из M камней эту карту и объяснил, где находится замечательная площадка (чтобы камень запомнил путь). Причем, чтобы главные камни нижних площадок не имели к нему претензий из-за такого нашествия, некоторым камням он показал на другие площадки, чем остальным. Чтобы не создать лавину, он сказал камням катиться с небольшим интервалом между собой. Немного подумав, он решил, что можно пускать камни парами, чтобы пространство быстрее освободилось. Камни ему поверили и стали собираться в дорогу.

Камни не любят скучать, поэтому каждая пара решила посчитать, сколько времени они будут катиться вместе, и, может быть, перестроить пары, чтобы увеличить это время. На то, чтобы скатиться по проходу с одной площадки в следующую, не заходя по пути на другие площадки, камень тратит одну минуту. Но складывать числа камни не умеют, в этом им требуется ваша помощь.

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

В первой строке входного файла записаны два целых числа - N и K , где 1 ≤ N ≤25000, K = M / 2, 0 ≤ M ≤ 2000 . В следующих ( N –1) строках находятся пары чисел i и j , означающие, что из i -й площадки можно напрямую скатиться на j -ю. Площадки занумерованы числами от 1 до N , верхняя площадка, откуда катятся камни, может иметь любой номер. Записанных пар номеров площадок достаточно, чтобы определить путь из самой верхней площадки до любой другой. Дальше идут K строк, на каждой строке через пробел записана пара чисел a и b (1 ≤ a , b N ) , обозначающая пункты назначения для очередной пары камней: первый камень катится на площадку a , а второй — на площадку b .

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

В выходной файл нужно вывести K строк, на каждой строке должно находиться по три целых числа a , b и c , записанных через пробел. Эти числа означают, что пара камней, направляющихся на площадки a и b , будет катиться вместе c минут. Тройки чисел нужно выдавать в том же порядке, в котором перечислены соответствующие им пары во входном файле.

Примеры
Входные данные
6 2
1 2
1 3
1 4
3 5
3 6
2 4
5 6
Выходные данные
2 4 0
5 6 1
ограничение по времени на тест
3.0 second;
ограничение по памяти на тест
128 megabytes

Гора состоит из площадок, соединенных между собой узкими проходами. На каждой площадке лежит какое-то количество камней. У разных площадок разный рейтинг, зависящий от высоты площадки — чем выше площадка, тем больше ее рейтинг среди камней. Очевидно, что на площадках с более высоким рейтингом лежит большее количество камней.

В один солнечный день главный камень одной из площадок обратил внимание, что вокруг стало очень тесно. Но камни не могут катиться вверх, а на нижние площадки они катиться не хотят из-за плохого рейтинга. Поэтому главный камень пошел на хитрость. Он выбрал M камней и сказал каждому из них, что где-то внизу появилась замечательная площадка с самым высоким рейтингом на горе. Для полной правдоподобности он составил карту площадок, на которые можно скатиться с его площадки. Всего (включая переполненную площадку) оказалось N площадок. Поскольку главный камень ленивый, он не стал рисовать все пути между площадками, а просто нарисовал минимальное количество проходов между площадками, чтобы из его площадки можно было добраться в любую, находящуюся ниже. Он показал каждому из M камней эту карту и объяснил, где находится замечательная площадка (чтобы камень запомнил путь). Причем, чтобы главные камни нижних площадок не имели к нему претензий из-за такого нашествия, некоторым камням он показал на другие площадки, чем остальным. Чтобы не создать лавину, он сказал камням катиться с небольшим интервалом между собой. Немного подумав, он решил, что можно пускать камни парами, чтобы пространство быстрее освободилось. Камни ему поверили и стали собираться в дорогу.

Камни не любят скучать, поэтому каждая пара решила посчитать, сколько времени они будут катиться вместе, и, может быть, перестроить пары, чтобы увеличить это время. На то, чтобы скатиться по проходу с одной площадки в следующую, не заходя по пути на другие площадки, камень тратит одну минуту. Но складывать числа камни не умеют, в этом им требуется ваша помощь.

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

В первой строке входного файла записаны два целых числа — N и K , где 1 ≤ N ≤ 500000 , K = M / 2 , 0 ≤ M ≤ 1000000 . В следующих ( N –1) строках находятся пары чисел i и j , означающие, что из i -й площадки можно напрямую скатиться на j -ю. Площадки занумерованы числами от 1 до N , верхняя площадка, откуда катятся камни, может иметь любой номер. Записанных пар номеров площадок достаточно, чтобы определить путь из самой верхней площадки до любой другой. Дальше идут K строк, на каждой строке через пробел записана пара чисел a и b (1 ≤ a , b N ) , обозначающая пункты назначения для очередной пары камней: первый камень катится на площадку a , а второй — на площадку b .

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

В выходной файл нужно вывести K строк, на каждой строке должно находиться по три целых числа a , b и c , записанных через пробел. Эти числа означают, что пара камней, направляющихся на площадки a и b , будет катиться вместе c минут. Тройки чисел нужно выдавать в том же порядке, в котором перечислены соответствующие им пары во входном файле.

Подзадача 1

1 ≤ N ≤ 25 000, 1 ≤ M ≤ 2 000. Решение оценивается в 55 баллов.

Подзадача 2

Дополнительные ограничения отсутствуют. Решение оценивается в 45 баллов.

Примеры
Входные данные
6 2
1 2
1 3
1 4
3 5
3 6
2 4
5 6
Выходные данные
2 4 0
5 6 1
ограничение по времени на тест
5.0 second;
ограничение по памяти на тест
256 megabytes

Дано дерево из n вершин. У каждой вершины есть цвет. Нужно обработать q запросов ( v i , c i ): найти расстояние от v i до ближайшей к v i вершины цвета c i . Расстоянием между вершинами называется минимальное количество рёбер в пути между ними.

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

На первой строке число n ( 1 ≤ n ≤ 10 5 ), следующая строка содержит числа p 1 , p 2 , ..., p n - 1 . 0 ≤ p i < i . p i – отец вершины i в дереве. Далее строка с числами a 0 , a 1 , ..., a n - 1 . 0 ≤ a i < n . a i – цвет вершины i . Далее строка с числом q ( 1 ≤ q ≤ 10 5 ). Следующие q строк содержат запросы v iq i ( 0 ≤ v i < n , 0 ≤ c i < n ).

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

Для каждого запроса выведите одно число – расстояние до ближайшей вершины нужного цвета, или - 1 , если в дереве нет вершин такого цвета.

Решения, работающие при \(1 \leq n \leq 200\), будут набирать не менее 30 баллов

Примеры
Входные данные
5
0 1 1 3
1 2 3 2 1
9
0 1
0 2
0 3
1 0
2 1
2 2
3 3
3 1
4 2
Выходные данные
0 1 2 -1 2 1 2 1 1 
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

На родной планете Чубакки растет очень большое дерево, на ветках которого вуки строят свои домики. Чубакке стало интересно, как быстро можно попасть из некоторых домиков в другие. Вам придется ответить на несколько его вопросов, чтобы он вас отпустил.

Вам дано дерево с N вершинами порядка K , то есть каждая вершина дерева может иметь не более K потомков. Дерево создано по принципу "минимальной энергии": вершины в нем располагается на новом уровне только тогда, когда все места на предыдущем уровне (слева направо) заняты. В таком же порядке вершины дерева пронумерованы, начиная с 1.

Вам необходимо ответить на Q запросов вида " x y ", где ответом является расстояние (количество ребер в минимальном пути) в данном дереве между вершинами с номерами x и y .

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

Первая строка содержит три целых числа: N ( 1 ≤ N ≤ 10 15 ), K ( 1 ≤ K ≤ 1000 ) и Q ( 1 ≤ Q ≤ 100000 ). Каждая из следующих Q строк содержит пару чисел x y ( 1 ≤ x , y N , x y ) - запросы, описанные в условии.

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

Выведите Q строк, в каждой из которых одно целое число - ответ на соответствующий запрос.

Примечание

Решения, работающие при 1 ≤ N , Q ≤ 1000 , будут оцениваться в 20 баллов. Решения, работающие при 1 ≤ N , Q ≤ 100000 , будут оцениваться в 50 баллов.

Примеры
Входные данные
7 2 3
1 2
2 1
4 7
Выходные данные
1
1
4
Входные данные
9 3 3
8 9
5 7
8 4
Выходные данные
2
2
3
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

В Флатландии идет пора реформ. Недавно была проведена реформа дорог, так что теперь по дорогам страны из любого города можно добраться в любой другой, причем только одним способом. Также была проведена реформа волшебников, так что в каждом городе остался ровно один волшебник. Теперь же началась реформа почтовой системы.

Недавно образованное почтовое агентство «Экс-Федя» предлагает уникальную услугу — коллективную посылку. Эта услуга позволяет отправлять посылки жителям всех городов на каком-либо пути по цене обычной посылки. Удивительно, но пользоваться такой услугой стали только волшебники Флатландии, которые стали в большом количестве отправлять друг другу магические кактусы. Агентство столкнулось с непредвиденной проблемой: как известно, все волшебники живут в башнях и мало того, что не строят в них лестницы, так еще время от времени меняют их высоту. Поэтому, чтобы доставить посылку волшебнику, который живет в башне высотой h , курьеру агентства требуется иметь с собой не менее h метров веревки.

Вам поручено руководить отделом логистики — по имеющимся данным о высотах башен и об их изменениях вам нужно определять минимальную длину веревки, которую нужно выдать курьеру, который доставляет посылки между городами i и j .

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

Первая строка входного файла содержит число n — количество городов в Флатландии ( 1 ≤ n ≤ 50 000 ). Во второй строке находится n положительных чисел, не превосходящих 10 5 — высоты башен в городах. В следующих n - 1 строках содержится по два числа u i и v i — описание i -й дороги, 1 ≤ u i , v i n , u i v i . В следующий строке содержится число k — количество запросов ( 1 ≤ k ≤ 100 000 ). В следующих k строках содержатся описания запросов в следующем формате:

  • Уведомление от волшебника из города i о том, что высота его башни стала равна h , имеет вид ! i h , 1 ≤ i n , 1 ≤ h ≤ 10 5 .
  • Запрос от курьера о выдаче веревки для доставки посылок во все города на пути от i до j включительно имеет вид ? i j , 1 ≤ i , j n .

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

Для каждого запроса доставки посылок выведите минимальную длину веревки, которую необходимо выдать курьеру.

Группы тестов (Все группы независимы)

20 баллов — ( 1 ≤ n, k ≤ 100) .

30 баллов — каждый город соединен дорогами не более чем с двумя другими.

50 баллов — полные ограничения.

Примеры
Входные данные
3
1 2 3
1 3
2 3
5
? 1 2
! 1 5
? 2 3
! 3 2
? 1 2
Выходные данные
3
3
5
Входные данные
1
100
5
! 1 1
? 1 1
! 1 1000
? 1 1
! 1 1
Выходные данные
1
1000

Страница: << 1 2 3 4 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест