Многие пользуются std::cin для ввода чисел. Известно, что он работает медленнее, чем scanf, но до настоящего момента я не подозревал, насколько медленнее.

Задача: 472D - Уроки дизайна задач: обратные задачи

Решение с cin не проходит ограничение по времени: 11495679

Решение с scanf проходит ограничение по времени с большим запасом: 11495791

Отличие между этими версиями состоит только в замене cin на scanf. Долгое время я искал проблему в самом алгоритме, а оказалось, что она в вводе/выводе.

Позже я прочитал, как ускорить cin (и cout), отключив синхронизацию с stdio. Однако этого оказалось недостаточно: тест 9 был пройден, но на тесте 10 уже свалилась: 11495880

Мораль: если входных данных много, то надо использовать scanf.

Кстати, меня удивило, что при превышении лимита по времени ответ всё равно выводится: 11495679, тест 9. Программа выводит ответ непосредственно перед завершением, значит при превышении лимита времени (тем более, на чтении входных данных) она не должна была бы успеть распечатать ответ.

Решение задачи.

1. Проверим, что диагональные элементы матрицы равны 0, а остальные — не равны.
2. Проверим, что матрица симметрична.
3. Назначим первую вершину корнем.
4. Найдем одну из ближайших к ней вершин и назначим её ближайшим соседом (её индекс хранится в cmp).
5. Для каждой вершины i, не являющейся корнем или ближайшим соседом корня, проверим верность хотя бы одного из утверждений: (1) маршрут от корня к i проходит через ближайшего соседа: D[root][cmp] + D[cmp][i] == D[root][i] и (2) маршрут от i к ближайшему соседу проходит через корень: D[i][root] + D[root][cmp] == D[i][cmp]
6. Назначим корнем следующую вершину и перейдем к нашу 4.

PS. Можно ли в тексте сделать вложенный список?

UPD. В комментариях предложили, как дополнительно ускорить cin: использовать cin.tie(NULL) в сочетании с ios_base::sync_with_stdio(0). 11496401

UPD2. Когда даже scanf оказывается слишком медленным, можно использовать побайтовый fread и парсить вручную. 11496768