Maxflow problem

Revision en1, by dsu123, 2021-01-17 21:55:39

This is a query regarding the problem https://mirror.codeforces.com/contest/498/problem/C (Array and Operations). I have implemented the idea suggested in the editorial for the problem https://mirror.codeforces.com/blog/entry/15353. The maximum number of vertices in my graph is $$$O(NlogA)$$$ and the maximum number of edges is $$$O(Mlog^2A)$$$. Here $$$A$$$ is the maximum value in the array. Now, if we use Edmond Karp then the total complexity should be $$$O(NMlog^5A)$$$. This should clearly time-out. But my solution https://mirror.codeforces.com/contest/498/submission/104527559 gets AC within $$$140$$$ ms. Is there anything I have missed out?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English dsu123 2021-01-17 21:55:39 625 Initial revision (published)