ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1416. Confidential

Is O(N^2) the fastest solution ?
Posted by N.M.Hieu ( DHSP ) 14 May 2006 20:21
I think O(N^2) ( Prim + DFS )is the fastest way to solve this problem , is it right ?
Re: Is O(N^2) the fastest solution ?
Posted by Alexey 14 May 2006 20:30

Tell me, Why Kruscal+DFS doesn't work? I have TLE#12.
Should I write Prim?
Re: Is O(N^2) the fastest solution ?
Posted by N.M.Hieu ( DHSP ) 14 May 2006 22:20
I think Kruskal + DFS is enough.
Maybe you need to optimize your code.
Nguyen Dinh Tu ( DHSP ), my fiend , has got AC with the complexity O(N^3)( 0.89s ) . He used Prim , too.
Re: Is O(N^2) the fastest solution ?
Posted by Alexey 15 May 2006 18:14
OK, then tell me, please, how to find the second answer?
I use DFS... May be I should delete the largest vertic and
run Kruscal again?
Re: Is O(N^2) the fastest solution ?
Posted by Ludovic 9 Sep 2006 07:51
You may try adding each non-MST edge to the MST and delete the longest MST edge in the cycle.
Re: Is O(N^2) the fastest solution ?
Posted by -XraY- 25 Oct 2011 16:23
I don't know how, but my O(n^2) solution works 0.312 sec)