Hi everyone, as mentioned in the title I have been recently trying to solve ADAGROW on SPOJ, but my best attempt was to model the solution as Min Cost Max Flow problem, with a graph made of roughly $$$10^6$$$ edges — $$$O(N^2)$$$.

The total flow that can be sent is only $$$K \le 20$$$, but my solution was still far from fitting into the TL. I realized that some of edges could be skipped and that if the input was random skipping those edges would've made the network small enough to pass — this way, I managed to AC the problem.

The worst case of my solution still has $$$~N^2/4$$$ edges, so I was wondering if anyone had tips on how else to model it so that the number of edges is always something reasonable.

Thanks!

I remember that something like an year ago someone showed me a problem on some OJ where it was required to answer queries on a tree. This might sound super common, but the cool thing about the problem was that a lot of different types of queries could be asked, iirc there were at least 7 or even 8 different kind of queries.

Does anyone recall a similar problem? Thanks!