O(N + M) getting TLE on 2500 ms

Revision en1, by brdy, 2018-08-23 00:06:09

For some strange reason, my code to compress a directed graph into a DAG and run some process on it gets TLE on this problem 894E - Ральф и грибы.

This is strange, because N = M = 1e6 at maximum. In addition, I used to have a log factor which I removed (using math instead), but it still gets TLE on test case 14.

My solution to the problem (41978175) is pretty much same idea as editorial, up until the last point. Instead of running toposort/dp on the DAG, I just traverse down and take the maximum path, but complexity of the function should still be O(N+M).

I am baffled by how this would TLE, can anybody give me some advice on constant optimizations or how the complexity could possibly be worse than imagined?

Tags #implementation, #tarjan, #bug, #tle, #bitset, #oleg


  Rev. Lang. By When Δ Comment
en1 English brdy 2018-08-23 00:06:09 765 Initial revision (published)