O(N + M) getting TLE on 2500 ms

Правка en1, от 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 - Ralph and Mushrooms.

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?

Теги #implementation, #tarjan, #bug, #tle, #bitset, #oleg

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский brdy 2018-08-23 00:06:09 765 Initial revision (published)