scanf вместо std::cin для чтения больших данныхinstead of std::cin for large inputs
Difference between ru1 and en1, changed 1,864 character(s)
Многие пользуются std::cin для ввода чисел. Известно, что он работает медленнее, чем scanf, но до настоящего момента я не подозревал, насколько медленнее.↵
↵
Задача: [problem:472D]↵
↵
Решение с cin не проходит ограничение по времени: [submission:11495679]↵
↵
Решение с scanf проходит ограничение по времени с большим запасом: [submission:11495791]↵
↵
Отличие между этими версиями состоит только в заменеMany people use std::cin to input numbers. cin is known to be slower, than scanf, however until now I did not realize how much slower it is.↵
↵
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 наor scanf. Долгое время я искал проблему в самом алгоритме, а оказалось, что она в вводе/выводе.↵
↵
Позже я прочитал, [как ускоритьI spent lot of time looking for a problem with algorithm itself, but slow io turned out to be the reason.  ↵
↵
Then I found [how to speen up cin](http://mirror.codeforces.com/blog/entry/10) (иand cout), отключив синхронизацию с stdio. Однако этого оказалось недостаточно: тест 9 был пройден, но на тесте 10 уже свалилась: [submission:11495880]↵
↵
**Мораль: если входных данных много, то надо использовать scanf**.↵
↵
Кстати, меня удивило, что при превышении лимита по времени ответ всё равно выводится: [submission:11495679], тест 9. Программа выводит ответ непосредственно перед завершением, значит при превышении лимита времени (тем более, на чтении входных данных) она не должна была бы успеть распечатать ответ.↵
↵
Решение задачи.↵
↵
1. Проверим, что диагональные элементы матрицы равны 0, а остальные — не равны.↵
2. Проверим, что матрица симметрична.↵
3. Назначим первую вершину корнем.↵
4. Найдем одну из ближайших к ней вершин и назначим её ближайшим соседом (её индекс хранится в cmp).↵
5. Для каждой вершины i, не являющейся корнем или ближайшим соседом корня, проверим верность хотя бы одного из утверждений: (1) маршрут от корня к i проходит через ближайшего соседа: turn off synchronization with cstdio streams. However it is not sufficient for this problem. test 9 was passed, but test 10 failed: [submission:11495880]↵
↵
**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] иand (2) маршрут от i к ближайшему соседу проходит через кореньpath from the i to the nearest neighbour includes the root: D[i][root] + D[root][cmp] == D[i][cmp]↵
67. Назначим корнем следующую вершину и перейдем к нашу 4.↵
↵
PS. Можно ли в тексте сделать вложенный списокSet root to next vertex and go to 4.↵
↵
PS. How to make nested list in this markdown?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English starius 2015-06-08 14:21:49 231 cin.tie(NULL), fread
ru2 Russian starius 2015-06-08 14:18:42 302 cin.tie(NULL), fread
en1 English starius 2015-06-08 13:19:54 1864 Initial revision for English translation
ru1 Russian starius 2015-06-08 13:18:10 1869 Первая редакция (опубликовано)