There are 2 different ways to solve this problem. The first one is to optimize one of the standard Maxflow algorithms to pass TL. The second one is to use the planarity of graph, design an algorithm that is asymptotically faster than the standard ones, and get AC with it.

Exuse me!.Brilliant the problem, thank the authors.
We build dual graph and use Dejkstra in it- O(nlog(n)).
But computing dual graph is separated difficult problem
from computational geometry connected with walking on grid
with extacting faces.

Now I am implementing this approach.
In test 14 I have situation when starting from some
edge and making maximal possible turn to left we don't
return to starting edge. Is it possible in
comlex geometry or bug in program.

Edited by author 18.07.2009 11:05

The complexity of my solution is approximately O((2^N)*(2^N)*N*N).
More exactly it is O(Mk*N*N), where Mk = C(N,N-1)+C(N,N-2)*2^2+C(N,N-3)*2^3+...+C(N,2)*2^(N-2)+C(N,1)*2^(N-1)
where C(N,M) - is the number of combinations :)

I use as much as O((2^N)*(2^N)) memory.

Good luck!

1
Smmam WA 7

Answer: 1 1

Thank for your Reply.
Yeah, I used scanf/printf for IO. I think I should have reduce the number of maps in my code. I used following structures:
map < string , int > city_to_index ;// locate the position of each city in the heap.
map < string , string > where;// locate the city in where the billionaire is
map < string , LL > how_much;// the amount of money each billionaire has
map < string , int > answer;// the answers
Do you have any idea to reduce them?
One problem that I think that my cause TLE is that I built my heap in array and each time I update my heap I should have change the values in city_to_index. Maybe if I implement it with pointers would be better. I mean, it may be better to build the heap with pointers and for swapping the nodes their addresses in city_to_index remains unchanged. (map<string,node*> city_to_index) IT IS SOMEHOW COMPLICATED FOR ME TO IMPLEMENT IN THAT WAY, DO YOU HAVE ANOTHER IDEA?

Edited by author 22.01.2009 19:23

Thanks

So Am I - how did you improve the performance ?

How did you speed it up?

optimal program use 4 or less cells

It's possible to work with DP over 27*27*27*4*50 states for 4 modifiable cells. Yes, this uses some interesting assumption but it is provable.

P.S: got AC

Edited by author 14.07.2008 02:52

Edited by author 14.07.2008 03:54

Thank you!!! I'm real lol))))