|
|
back to boardBest algo you have(mine is O(Q^2*N)) Posted by Elias 25 Feb 2016 12:33 Hello! Can somebody tell me if there is a faster algo than O(Q^2*N)? My algo works pretty fast, but I wondered if there is a better way to do it. Re: Best algo you have(mine is O(Q^2*N)) Posted by Arseniy 11 Mar 2016 21:49 My solution Q*N, lol
Or no
I'm not sure
Edited by author 11.03.2016 21:50
Edited by author 11.03.2016 21:50 My algo is O(N^3) and I got AC 0.001s! Posted by c_pp 25 Dec 2016 17:35 My algo is fills dp[vertex][presaved edges] array (result is dp[1][Q]), where total loops N^3/6 < 2*10^5.
There maximum presaved edges = Q, but more vertexes have less edges than Q.
Let edges[v] - number of edges of v vertex.
So there O( N * sum( edges[ v ] * ( edges[ v ] + 1 ) / 2 ) ) = O( N^3 / 6 ). |
|
|
