dsu123's blog

By dsu123, history, 4 years ago, In English

This is a query regarding the problem https://codeforces.net/contest/498/problem/C (Array and Operations). I have implemented the idea suggested in the editorial for the problem https://codeforces.net/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://codeforces.net/contest/498/submission/104527559 gets AC within $$$140$$$ ms. Is there anything I have missed out?

Full text and comments »

  • Vote: I like it
  • -3
  • Vote: I do not like it