I tried to solve problem A from the Google CodeJam finals 2018, after reading the analysis.

In the analysis it says: We can binary search for L and U independently using their original definitions, which yields an algorithm that takes time O(S⁵ × log(R × C))

I don't understand how they arrive at this bound. The compressed graph has O(S²) vertices and O(S³) edges. Running Edmonds-Karp in each binary search iteration would therefore give a complexity of O(V × E²) = O(S⁸). Running Dinic would give O(E × V²) = O(S⁷). How do they get S⁵?

I implemented a solution both with Dinic and using Edmonds-Karp. Dinic was accepted, Edmonds-Karp got TLE for the large problem.