↵
Задача: [problem:472D]↵
↵
Решение с cin не проходит ограничение по времени: [submission:11495679]↵
↵
Решение с scanf проходит ограничение по времени с большим запасом: [submission:11495791]↵
↵
Отличие между этими версиями состоит только в замене
↵
The problem: [problem:472D]↵
↵
The solution using cin exceeds time limit: [submission:11495679]↵
↵
The solution using scanf satisfies time limit more than enough: [submission:11495791]↵
↵
The only difference between these solutions is using cin
↵
Позже я прочитал, [как ускорить
↵
Then I found [how to speen up cin](http://codeforces.net/blog/entry/10) (
↵
**Мораль: если входных данных много, то надо использовать scanf**.↵
↵
Кстати, меня удивило, что при превышении лимита по времени ответ всё равно выводится: [submission:11495679], тест 9. Программа выводит ответ непосредственно перед завершением, значит при превышении лимита времени (тем более, на чтении входных данных) она не должна была бы успеть распечатать ответ.↵
↵
Решение задачи.↵
↵
1. Проверим, что диагональные элементы матрицы равны 0, а остальные — не равны.↵
2. Проверим, что матрица симметрична.↵
3. Назначим первую вершину корнем.↵
4. Найдем одну из ближайших к ней вершин и назначим её ближайшим соседом (её индекс хранится в cmp).↵
5. Для каждой вершины i, не являющейся корнем или ближайшим соседом корня, проверим верность хотя бы одного из утверждений: (1) маршрут от корня к i проходит через ближайшего соседа
↵
**Use scanf for large inputs**.↵
↵
By the way, why the output is shown in the time limit is exceeded? [submission:11495679], test 9. The program prints the answer immediately before exiting, so if the time limit is exceeded (especially if it happens when it reads input data), it must not be having time to print the answer.↵
↵
The solution.↵
↵
1. Check diagonal elements of the matrix are equal to 0 and other elements are not.↵
2. Check that matrix is symmetrical.↵
3. Set root to the first vertex.↵
4. Find a vertex nearest to the root (or one of such possible vertices) and set it to "nearest neighbour" (variable cmp in the code).↵
5. For each vertex i not equal to the root and to the nearest neighbour, check that at least one of the following conditions is satisfied: (1) path from the root to i includes the nearest neighbour: D[root][cmp] + D[cmp][i] == D[root][i]
↵
PS. Можно ли в тексте сделать вложенный список
↵
PS. How to make nested list in this markdown?
