scanf instead of std::cin for large inputs

Revision en1, by starius, 2015-06-08 13:19:54

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: 472D - Design Tutorial: Inverse the Problem

The solution using cin exceeds time limit: 11495679

The solution using scanf satisfies time limit more than enough: 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 (and cout): turn off synchronization with cstdio streams. However it is not sufficient for this problem. test 9 was passed, but test 10 failed: 11495880

Use scanf for large inputs.

By the way, why the output is shown in the time limit is exceeded? 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) path from the i to the nearest neighbour includes the root: D[i][root] + D[root][cmp] == D[i][cmp]
  6. 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 Первая редакция (опубликовано)