Yes. Compressing coordinates and painting segments straightforwardly is enough.

really good hint)
thanx

I will tell you the solution because this problem should have time limit of around 3-5 seconds. I struggled for almost two days making that algo suffice all tests, and still I had to precompute an empty 12x12 grid, and my AC solution ran for exactly 1 second :))

Go row-by-row with state representing connected components above. These will be something like 11022, 12021, 10220133, etc... Where 0 stands for no exit from above and 1..n stand for connected component number. Actually, every connected component will have exactly two exits downwards, and they will be placed in stack order. Cases like 1212 are impossible because it would mean that paths 1..1 and 2..2 intersect somewhere above. So, this gives us a way to effectively enumerate all of components using at most 2^2 * 3^10 states. Digit 0 means skip. Digit 1 means start new component. Digit 2 means close last open component (remeber their stack order). First digit can't be 2 and last digit can't be 1.

This is enough to keep values about previous and next row with cache of next_x[12] - a matching of exits for each column. Also, don't forget to keep array of indices with non-zero values for previous and the next row, this optimizes things a little as you will run only through reachable states.

Once you complete current row, paint everything to find resulting components matching with exits from the row just painted. It can be done via BFS, but I couldn't meet TL with that, so I had to optimize it - all paths are chains, so just walk straight. For the last row a path should be a chain loop covering of all upper exits.

Internal transfers should keep all components alive, that is - there must be no loops. This also allows to optimize recursive steps for building current row by remembering last connected upper component connected by "rhhhh..." - so just don't allow closing it towards itself, unless it is the last row.

Also, do not forget to skip first and last rows full of **********.

I took in internet one of the  best Ford-Falkerson with BFS, based on
priority queue and got Ac immidiately(but time is not very good)

there are some anti-bfs tests, try to cheat somehow :)

My simple BFS implementation of F-F also TLed, but Dinic's modification got AC

Edited by author 12.07.2012 19:25

If you FF algorithm runs slow you can add scaling, either bit-scaling or simple capacity scaling, this alone should be enough to deal with all possible anti-FF networks.

My 0.093  N square solution:

1) Compute MST with Kruskal in E logE.
2) For each pair of vertices in MST compute dp[u][v] the cost of largest edge on path from u to v. This can be done by calling N depth first searches. DFS runs in O(E) and there is N - 1 edge in a MST. So this step takes (N^2) time.
3) For each edge (u, v) that isn't in a MST try to relax answer with { MST_COST - dp[u][v] + weight(u, v) }. This step is done in O(E).

So, the running time of this solution is O(ElogE + E + N^2) = O(N^2).

Instead of changing text inside the program you can simply run it and redirect its input or output, for example, run

python3 prog.py < input.txt > output.txt

If you absolutely cannot use shell then you can redirect input/output by assignment, but remember to remove this part before submission.

import sys
sys.stdin = open('input.txt')
sys.stdout = open('output.txt','w')

a=int(input())
print(a+1)

1
Dumbo --->>> is not working

3Q for your help!

1 1 469
butter

1 1 470
bread

me too!

try this test case:
5
170
170
180
175
170
175
175
170
175
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1

1       1       170     1       1
1       170     175     170     1
1       175     180     175     170
1       1       175     1       1
1       1       1       1       1

Dude, the same to me :((

abcabc
bc
answer:
aabc