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.
- Check diagonal elements of the matrix are equal to 0 and other elements are not.
- Check that matrix is symmetrical.
- Set root to the first vertex.
- Find a vertex nearest to the root (or one of such possible vertices) and set it to "nearest neighbour" (variable cmp in the code).
- 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]
- Set root to next vertex and go to 4.
PS. How to make nested list in this markdown?
UPD. Additional speed up of cin: use cin.tie(NULL) in addition to ios_base::sync_with_stdio(0). 11496401
UPD2. Reading bytes with fread are manual parsing is even faster than scanf. 11496768
