Organizing Committee won't publish an editorial after the end of the Olympiad. We will publish the tasks, tests and author's solutions on APIO2018 website.

I will give a link for the Olympiad materials here.

Everything will be allright:)

We will publish the Olympiad materials until 20 of the May

Hi, you will get a username and password after the registration closes. I think,we will send all necessary information at 7-8pm(UTC +3).

wait 2hr

why do you need to split on AP btw? because.. in any case.. after creation of a bridge tree, there will be no case that is not eliminated by the bridge tree but eliminated by the AP-splitting. What i mean is.. if S,F where on different sides of AP then its all good. And even if they are on the same side, We can still go form S, through the AP(which is taken to be C) and then to F, without revisiting. if we were indeed revisiting, then that means there was only one path.. which is again a bridge, and so that case is already eliminated by the bridge tree.

Please correct if wrong.

Sorry for my poor English

2nd problem can be solved in the following way: First, consider how to solve subtask 4(all circles have the same radius R): We can divide the Cartesian plane by square with R*R. Then, for each circle i that has not been removed yet, let's denote the circle i in block x_i, y_i. Other circles which might be removed by circle i must be in block ( x_i ± 2 , y_i ± 2 ).

Now, let’s try to solve the whole task. Let’s denote one operation as: one circle i remove other circles in blocks ( x_i ± 2 , y_i ± 2 ). First, let’s sort the circles by the radius. Let’s divide the Cartesian plane with R = r_max. Then do the operation. If the operation had be done more than 1024 times and now the current r * 100 <= r_max. Then we set r_max = r and divide the Cartesian plane with new radius r_max again. The source of parameter 1024 and 100 is found during the contest. (If the parameter 1024 is changed to 3000 or more, it will TLE on test 88).

I got AC on 2nd problem by the above method.

Instead of dividing into R*R blocks, we can divide blocks using logs.

Assume that at first, we have one big block, with coordinate [0,0] to [2^32, 2^32]

At each query, we can just divide each block into 2*2 smaller block until the side of each block is as small as possible but still bigger than current R. The rest of the solution is same as yp155136's one.

Please note that the division step can be done quickly using bitwise operator, combined with the idea of radix sort (base 2)

By using this method, we do not need to find the "magic" value for each division.

For Prob C, I got AC with an idea similar to radoslav11, however, I connect every nodes in one BCC to a virtual nodes so that I need to do DFS just one time.

What was your approach?

Hi!

We will publish the Olympiad materials until 20 of the May

Just imagine when vec.size()>=blocksize happens all the time. This is pure n^2.