The last part is a succession of max flow problems. And a linear seach is enough: you don't have to start from scratch every time, because adding edges to the graph doesn't affect the admissibility of the assignment.

More precisely, there is exactly one cycle in every connected component (and it's length may be less than 3).

I think that the way you modelled the chemicals problem as a graph problem is useful. I suggest you to solve two special cases first:

1. The graph is a cycle
2. The graph is a tree

And then you should be able to solve the original problem.

Suppose m is even. Let's call 'step' changing avery LR to UD and then every UD to LR, as done in matthew99's solution. We want to show that eventually all cells become L or R.

A cell is 'stable' if it is L or R and it stays the same after performing an arbitrary number of steps. Suppose by contradiction there is a cell that never become stable, and consider the first one which has this property (it means that all the cells on the left and those placed in some preceding row eventually become stable. We can assume they are already stable, provided a sufficient number of steps has been performed). This cell must be U, and we can also determine the type of many other nearby cells, as shown:

****************
****ULR.........
....DULR........
.....DULR.......
etc...

(asterisks denote stable cells, dots denote unknown cells).

The same pattern must continue in diagonal until the border of the grid is reached. But this is impossible because there's no way to tile the cells above that diagonal using dominos (if you color them like a chessboard, the number of black cells and the number of white cells would be different).

Actually, most of the people who solved it used c++

You can store many updates (say k updates) in one single node, and create its children only when you are attempting to insert the (k + 1)-th update. When querying, don't propagate the updates but consider all of them in O(k) time.
With this strategy, you should save a considerable amount of memory. You can find the best choice of k after some experiments.

This is not a valid position, although only one connected component of size 18 needs to be tiled (X=6 on a 4x6 grid):

......
.X.X..
.XXX..
.X....

During the contest I misread the limit for n (lenght of the string) in problem Div1-C, I thought it was n ≤ 10000.
However I wrote a quadratic solution similar to the first one explained in the editorial. Obviously I got a memory limit error, because a table of 10⁸ integers is too large...
In a hurry I edited the algorithm, and managed to solve the problem using a -sized table :)

Consider the devices starting from the top.
You want to compute the answers to this question, for i = 1... M:
"What is the minimal cost so that, if a ball appears in the leftmost column, it falls into device i?" Let's call the answer cL(i).
We have a nice formula for cL(i): 
- if A[i] = 0, then cL(i) = D[i]
- otherwise cL(i) = min{cL(j)} + D[i] for j < i such that A[i] ≤ C[j] ≤ B[i]
(that is, the ball falls from device j to device i)

Using a range tree you can calculate minimum in time.

Do the same for the right side and the final answer will be of the form cL(i) + cR(i) - D[i]

It works because (at least in the optimal set-up) the devices chosen for the left and right side are different, otherwise taking device i would be useless.

This was my key observation: it is sufficient that, if the ball appears in the leftmost and the rightmost column, it arrives in the same final column.

The link has been restored: today I've been able to download the test data.

Begin with the empty plane.
Every time you draw a circle you surely add one region, and in some cases you add two regions.
More precisely, you add two regions if and only if your new circle is touching two circles that are already in contact, directly or through a chain of circles that touch.
So using a disjoint set structure is quite natural...

I failed on the 4th problem just because I forgot to initialize my union-find disjoint set structure T_T

For the last one:

Order the points looking at the x-coordinate, and take the median point P. Then place a light at every point K such that y_K = y_P

Work similarly on the left and on the right recursively...

After the 0-command you should empty all the containers.

Without using trees:
Keep an array S in which every element is infinity at the beginning.
Then you read the input and every number you read, you insert it in the first position in S which contains an element greater than it (you can perform this with binary search). If you proceed in this way, S (not including the INFs) keeps the following properties at every step:
- It is an increasing subsequence;
- There exists an increasing subsequence (in the input read so far) with the same lenght of the sequence stored in S, and terminating in the same way of the sequence stored in S.
- Such increasing subsequence is as long as possible.
Note that S is not the LIS itself.

He sent me the same message! Of course I ignored him...