Задача A. Расстояние от корня ≡

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:256 Мб

Условие

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

Формат входного файла

В первой строке задано n "--- количество вершин в дереве. В следующих n − 1 строках заданы вершины, являющиеся предками вершин 2, 3, …, n. Вершина 1 является корнем дерева.

Формат выходного файла

В первой строке выведите максимальное расстояние от корня до остальных вершин дерева.

Во второй строке выведите, сколько вершин дерева находятся от корня на таком расстоянии.

В третьей строке выведите номера этих вершин через пробел в порядке возрастания.

Ограничения

1 ≤ n ≤ 105

Примеры тестов

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
3
1
1

1
2
2 3
2 
3
1
2

2
1
3

Задача B. Производство деталей ≡

Автор:Центральная предметно-методическая комиссия по информатике   Ограничение времени:2 сек
Входной файл:details.in   Ограничение памяти:256 Мб
Выходной файл:details.out  

Условие

Предприятие «Авто-2010» выпускает двигатели для известных во всем мире автомобилей. Двигатель состоит ровно из n деталей, пронумерованных от 1 до n, при этом деталь с номером i изготавливается за pi секунд. Специфика предприятия «Авто-2010» заключается в том, что там одновременно может изготавливаться лишь одна деталь двигателя. Для производства некоторых деталей необходимо иметь предварительно изготовленный набор других деталей.

Генеральный директор «Авто-2010» поставил перед предприятием амбициозную задачу — за наименьшее время изготовить деталь с номером 1, чтобы представить ее на выставке.

Требуется написать программу, которая по заданным зависимостям порядка производства между деталями найдет наименьшее время, за которое можно произвести деталь с номером 1.

Система оценивания

Решения, правильно работающие только для тестов, в которых n не превосходит 10, будут оцениваться из 40 баллов.

Решения, правильно работающие только для тестов, в которых n не превосходит 100, будут оцениваться из 60 баллов.

Решения, правильно работающие только для тестов, в которых n не превосходит 1000, будут оцениваться из 80 баллов.

Формат входного файла

Первая строка входного файла содержит число n — количество деталей двигателя. Вторая строка содержит n натуральных чисел p1, p2… pn, определяющих время изготовления каждой детали в секундах.

Каждая из последующих n строк входного файла описывает характеристики производства деталей. Здесь i-ая строка содержит число деталей ki, которые требуются для производства детали с номером i, а также их номера.

Известно, что не существует циклических зависимостей в производстве деталей.

Формат выходного файла

В первой строке выходного файла должны содержаться два числа: минимальное время (в секундах), необходимое для скорейшего производства детали с номером 1 и число k деталей, которые необходимо для этого произвести. Во второй строке требуется вывести через пробел k чисел — номера деталей в том порядке, в котором следует их производить для скорейшего производства детали с номером 1.

Ограничения

1 ≤ n ≤ 100000, 1 ≤ pi ≤ 109

Сумма всех чисел ki не превосходит 200000.

Примеры тестов

№ Входной файл (details.in) Выходной файл (details.out)
1 
3
100 200 300
1 2
0
2 2 1

300 2
2 1
2 
2
2 3
1 2
0

5 2
2 1
3 
4
2 3 4 5
2 3 2
1 3
0
2 1 3

9 3
3 2 1

Problem C. Dijkstra ≡

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:16 Mb
Output file:output.txt  

Statement

You are to write a program that receives a weighted directed graph and finds distances from source vertex S to all other vertices. Distance from S to some vertex W is the minimal length of path going from S to W. Length of path is the sum of weights of its edges.

Vertices are numbered with integers from 1 to N.

Input file format

First line of input file contains three integers N M and S, where M is the number of edges. Next M lines contain three integers each — starting vertex number, ending vertex number and weight of some edge respectively. All weights are positive. There is at most one edge connecting two vertices in every direction.

Output file format

Output file must contain N integers — distances from source vertex to all vertices. If some vertices are not reachable from S, corresponding numbers must be −1.

Constraints

1 ≤ N ≤ 1000. All weights are less or equal than 1000.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1 
5 3 1
1 2 5
1 3 7
3 4 10
 
0 5 7 17 -1

Problem D. Ford-Bellman ≡

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:8 Mb
Output file:output.txt  

Statement

You are to write a program that finds shortest distances from vertex S to all other vertices in a given directed weighted graph. Graph consists of N vertices, numbered from 1 to N, and M edges.

Input file format

Input file contains two integers N M S, followed my M triplets of integers ui vi wi — starting vertex, ending vertex and weight or the edge. There is at most one edge connecting any two vertices in every direction. There are no cycles of negative weight.

Output file format

Output file must contain a vector of N integers — distances from vertex S to other vertices. The distance from any vertex to itself is considered to be 0. If some vertex is not reachable from S, corresponding cell of the vector must contain empty space.

Constraints

0 ≤ N, M ≤ 1000. All weights are less than 1000 by absolute value.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1 
3 3 1
1 2 5
1 3 10
2 3 2
 
0 5 7

Задача E. Лабиринт ≡

Автор:Общеизвестная   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Лабиринт задан как двумерный массив символов '.' и '#', означающих пустое пространство и стену соответственно. В любой не занятой стеной клетке может находиться Искатель. Ему разрешено перемещаться по клеткам лабиринта в четырех направлениях: вверх, вниз, влево и вправо. Покидать лабиринт через внешнюю границу запрещено, ибо за его пределами находится сплошная стена. Требуется написать программу, которая по заданному лабиринту определяет существует ли путь от входа к выходу.

Формат входного файла

Первая строка входного файла содержит числа N и M - количества строк и столбцов в описании лабиринта соответственно. В следующих N строках содержатся по M символов из множества '.' (пустое пространство) , '#' (стена), 'S' (вход), 'F' (выход). В описании лабиринта присутствует ровно один символ 'S' и ровно один 'F'.

Формат выходного файла

Выведите в выходной файл текстовую строку 'YES', если существует путь от входа к выходу и 'NO' в противном случае.

Ограничения

1 ≤ N,M ≤ 1000

Примеры тестов

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
3 3
S#.
.#F
...
 
YES
2 
3 3
S#.
.#F
#..
 
NO
0.326s 0.011s 21