Многие пользуются std::cin для ввода чисел. Известно, что он работает медленнее, чем scanf, но до настоящего момента я не подозревал, насколько медленнее.
Задача: 472D - Design Tutorial: Inverse the Problem
Решение с cin не проходит ограничение по времени: 11495679
Решение с scanf проходит ограничение по времени с большим запасом: 11495791
Отличие между этими версиями состоит только в замене cin на scanf. Долгое время я искал проблему в самом алгоритме, а оказалось, что она в вводе/выводе.
Позже я прочитал, как ускорить cin (и cout), отключив синхронизацию с stdio. Однако этого оказалось недостаточно: тест 9 был пройден, но на тесте 10 уже свалилась: 11495880
Мораль: если входных данных много, то надо использовать scanf.
Кстати, меня удивило, что при превышении лимита по времени ответ всё равно выводится: 11495679, тест 9. Программа выводит ответ непосредственно перед завершением, значит при превышении лимита времени (тем более, на чтении входных данных) она не должна была бы успеть распечатать ответ.
Решение задачи.
- Проверим, что диагональные элементы матрицы равны 0, а остальные — не равны.
- Проверим, что матрица симметрична.
- Назначим первую вершину корнем.
- Найдем одну из ближайших к ней вершин и назначим её ближайшим соседом (её индекс хранится в cmp).
- Для каждой вершины i, не являющейся корнем или ближайшим соседом корня, проверим верность хотя бы одного из утверждений: (1) маршрут от корня к i проходит через ближайшего соседа: D[root][cmp] + D[cmp][i] == D[root][i] и (2) маршрут от i к ближайшему соседу проходит через корень: D[i][root] + D[root][cmp] == D[i][cmp]
- Назначим корнем следующую вершину и перейдем к нашу 4.
PS. Можно ли в тексте сделать вложенный список?
