Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

Why Dinic's Algorithm can pass the time limit for 720B — Cactusophobia?

Revision en1, by xuanquang1999, 2017-05-18 08:20:35

I'm trying to solve 720B — Cactusophobia from Russian Code Cup 2016 Final. I read the editorial and understood the flow solution for this problem. So I find some implementation for this problem. I read dreamoon_love_AA's solution (20732895), which used Dinic flow finding algorithm and run in 373ms. But, since Dinic algorithm run in O(n2m), and the graph can have up to 30000 vertices and edges, how could this run in time? Can someone enlighten me about this? Thanks in advance.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English xuanquang1999 2017-05-18 08:20:35 634 Initial revision (published)