search

Ra1nWarden / Online-Judges

My solutions to various online judge problems.
0 stars 0 forks source link

11504 TLE #11

Closed Ra1nWarden closed 9 years ago

Ra1nWarden commented 9 years ago

Reduce the graph into a DAG with SCC. Then this problem becomes Minimum Cover Path (which seems to be related to maximum bipartite matching.) I will revisit this later when I finish later chapters.

Ra1nWarden commented 9 years ago

TLE is due to the initialization of adjacency matrix. Choosing an adjacency seems to solve the time issue. However, I got a RE now instead. It might due to stack overflow as the recursive call to tarjan() gets way too deep. It is possible to make this iterative but I am not going to do that. Marked as fixed now.

Ra1nWarden commented 9 years ago

11770 got AC with the same code so my guess is correct.