Our code has been running for 30 minutes. Are there any teams that are having the same problem?

Yes, the problems' names of the Div2 contest are the same

In C we asked vertices for which we haven't got -1 and with maximal probability to reach edge to another component. This could be estimised by deg(v) — size_connected_component(v)

the same

Enumerate every field in table and xor indices of fields with ones

C++0x is basically C++11

A could be solved by interpolation. But under this constraints it is not better than gauss

In A we can use the fact that for every $$$k\geq d+1$$$ the following holds:

Then we choose random $$$a$$$ and $$$b$$$ and increase $$$k$$$ until we get equality modulo $$$mod$$$.

Fact: If $$$f(x)$$$ is a polynomial with degree $$$n$$$ then $$$f_{1}(x) = f(x + a) - f(x)$$$ (with any constant $$$a$$$) is a polynomial with degree $$$n-1$$$. If we define $$$f_{k}(x) = f_{k-1}(x + a) - f_{k-1}(x)$$$ then $$$f_{n}(x)$$$ will be a non-zero constant and $$$f_{n+1}(x) = 0$$$. The converse is also true. Therefore you can ask integers of form $$$b+at$$$ with some random constants $$$a$$$, $$$b$$$ and compute values of $$$f_{k}(x)$$$ accordingly. As soon as we find out $$$f_{k}(b) = f_{k}(b+a) = 0$$$ we can determine with high probability that $$$f(x)$$$ is of degree $$$k+1$$$.

Our solution is $$$O(N^{3/2})$$$.

Just do sqrt decomposition. It`s easy to deal using some precalculation before the queries with a pair of sqrt blocks (sort each block), with an element and a block (just sort each block and calculate values in increasing order of elements using some pointers for each block), and, finally, after the query you solve for a pair of "pieces of blocks" (using the fact that you can store all sorted prefixes and suffixes of all blocks in $$$O(N^{3/2})$$$ time and memory).

I got AC with your complexity, making the block size as low as possible and getting rid of the log in precalculation. The only part with log was sorting the "pieces of blocks" but that works quite fast since it uses little memory.

I solve D with Mo + Fenwick Tree + Hard Struggle

Top-left corner on this map (from here), medium square hall:

Dot on this map:

Here is a photo from this website:

No strategy, no secret, described in the statement: the graph is random and fixed in each test case.

three hours after the contest, our D still in queue

You are given $$$N$$$ functions of the form $$$f_i(\theta) = |r_i sin(\theta + \alpha_i)|$$$, and you want to find $$$\theta$$$ that maximizes the sum of $$$K$$$ smallest values among $$$f_i(\theta)$$$.

This sum is a "piecewise trigonometric function" with $$$O(N^2)$$$ pieces, so we can explicitly represent this function and compute the maximum.

The border between two pieces is a point that satisfies $$$f_i(\theta) = 0$$$ or $$$f_i(\theta) = f_j(\theta)$$$ for some $$$i,j$$$. We should list all such angles and sort them, and do various things carefully.

We received "Check failed" verdict for problem B solution on Java during the contest. Switched to C++ to get it judged.

Greedy. Let's store the answer for each vertex $$$v$$$ — the indices of taken decorations in its subtree. The answer for some vertex $$$v$$$ is the union of answers for all its children plus $$$w_v$$$ values of $$$v$$$. Truncate that list to $$$min(t, w_v)$$$ most expensive values, that'll be the answer. Use small-to-large and store the answer in a map to achieve $$$O(n \log^2 n)$$$.