Не могли бы вы разъяснить свои формулы?

У нас был похожий тест, но в нем было мало запросов на вывод. Видимо, из-за этого Ваше решение работает быстро. Наша ошибка. Большое спасибо за замечание.

13-ый символ считался — это заметно по сообщению. А вообще это извращение — читать вот таким образом с помощью System.in.

Solution is simple. let me explain it with a examples:

suppose we have filled all the empty blocks from column 0....i-1 and on ith column we have filled some of the empty blocks which is stored using mask 0,1,...,7

suppose if mask is currently 0 and i=2, so configuration could be something like this.

AA.X.
AA.0.
AA.X.

blocks with A are already filled.

now we have two options, we might use some vertical block or not:

1. if we use vertical block and put it in first 2 rows. new state ----> (i,3)
2. if we use vertical block and put it in last 2 rows. new state ----> (i,6)
3. if we choose not to use vertical block we have to use 3 horizontal one ----> (i+1,7)

now we are almost ready with solution and need to check while putting block if that box was empty earlier and which we put block near 0, we need to note this also.

I think, you should be able to understand my code now.

Assume that you have the distances from vertex with index 1 to every vertex u in a vector d[].

Define lca(x, y) the lowest common ancestor for vertex x and y. You must find out the distance from v to u.

The result is d[u] + d[v] — 2 * lca(u, v) because you add twice the distance from vertex 1 to lca(u, v) (that's where the 2 roads intersects). You can draw a tree on a paper and and work with some examples, it will be clearer.

Here is my solution: http://mirror.codeforces.com/contest/342/submission/4509629 The complexity seems to be O((n+m)*sqrt(m)). But it still gets TLE.

\begin{equation}m \cdot\sqrt{m}\cdot\log_2{(n)}\end{equation}

did u code in cpp?

My solution uses Heavy-light decomposition and segment trees. Complexity is O(N log^2 N). http://mirror.codeforces.com/contest/342/submission/6999318

Centroid Decomposition. O((n + m)*log^2 n). https://mirror.codeforces.com/contest/342/submission/293411563

In every decomposition tree node store a multiset of distances from this node to every red in the subtree the centroid of which the node is. So just go from any node up to the root — main centroid — and calculate distance from asked node to current centroid + shortest from current centroid to any red in its subtree (dist(u, v) = depth(u) + depth(v) — 2 * lca(u, v)). Lca binary for logn, decomposition tree height logn. So log^2 n every query. (Yeah, know, 10 years passed)

You can precalculate the lca of nodes in Mlogn

1 2

I'm a bit late but the solution is explained here.

Notice that dist(u, v) = dist(root, u) + dist(root, v) - 2 * dist(root, l), where l is the LCA of u and v

1) Use a DFS to find the distance from node 1 (the root) to every other node. Let rootDist[n] by the distance from node 1 to node n. The DFS should also find the parent of each node, and the depth of each node from the root. Let parent[n] be the parent of node n and depth[n] be the depth of node n.

Example DFS code:

//Let MAX be the number of maximum nodes
vector<int> adj[MAX];
int rootDist[MAX], parent[MAX], depth[MAX];

// cur = Current traversing node
// prev = Node traversed before this one
int dfs(int cur, int prev){
    parent[cur] = prev;

    for(int child : adj[cur]){
        if(child != prev){
            depth[child] = depth[cur] + 1;
            rootDist[child] = rootDist[cur] + 1;
            // Note: In the case of an unweighted tree,
            // depth[n] == rootDist[n]

            dfs(child, cur);

        }
    }
}

dfs(1, -1);

2) Build a sparse table. sparse[u][i] stores the 2**i-th parent of u, or -1 if that parent doesn't exist. Note that sparse[u][0] = parent[n]. The sparse table can be built by:

// N = number of nodes as given in input
// LN = ceil(log2(Max number of nodes))
// Using 1-indexing for nodes
int sparse[MAX][LN];
memset(sparse, -1, sizeof sparse);

for(int u = 1; u <= N; u++)
    sparse[u][0] = parent[u];

for(int i = 1; i < LN; i++)
    for(int u = 1; u <= N; u++)
        //if the node has a 2**(i - 1)th parent
        if(sparse[u][i - 1] != -1)
            // the 2**i-th parent of u is equal to
            // the 2**(i - 1)th parent of 2**(i - 1)th parent of u
            sparse[u][i] = sparse [ sparse[u][i - 1] ] [i - 1];

3) To query the lca of u and v, we do the following steps:

1. If u has a smaller depth than v, swap them
2. Find the ancestor of u with the same depth of v
3. If u and v are the same node, return it
4. Find the highest (least depth) ancestor of u and v (let's call them u' and v') such that u' is not v'
5. Return the parent of u' (which is equal to the parent of v')

Here is the code for the query:

int lca(int u, int v){
    if(depth[u] < depth[v])
        swap(u, v);

    // We use sparse table so we jump 2**i parents each time
    // Taking only log time
    for(int i = LN - 1; i >= 0; i--)
        // If the 2**i-th parent of u isn't higher than v
        if(depth[ sparse[u][i] ] >= depth[v])
            // Go up 2**i parents
            u = sparse[u][i];

    // At this point, depth[u] == depth[v]
    // If they happen to be the same node, that is the LCA
    if(u == v)
        return u;

    for(int i = LN - 1; i >= 0; i--){
        // If their ancestors aren't the same
        if(sparse[u][i] != sparse[v][i]){
            // Go up to their ancestor
            u = sparse[u][i];
            v = sparse[v][i];
        }
    }

    // At this point, they're at the highest ancestor
    // such that they're not the same, so one parent above
    // must be their LCA

    // 2**0 = 1, return first parent of u
    return sparse[u][0];
    // this is also equal to sparse[v][0]
}

And finally, to put it all together, to query distance

int dist(int u, int v){
    int l = lca(u, v);
    return rootDist[u] + rootDist[v] - 2 * rootDist[l];
}

Building the LCA sparse table takes O(n log n) time while querying takes O(log n) time

(I wrote this from memory; please tell me if there are any mistakes or if any part is confusing)

Source/Additional reading

Store all nodes which are currently red in a vector redlist. Create an queue bfslist for bfs, and create a array dist[v] = Distance from v to the nearest red node, 0 if v is itself red and initialize an empty queue. Now for all red vertices v, let dist[v] = 0 and push all the neighbours u of the red vertices which are not red into this queue, and for all such u, let dist[u] = 1, isdiscovered[u] = 1. Now it's just regular bfs: while the queue is nonempty, pop the first element w from the queue, and add all the neighbours y of w not already discovered to the queue, and let dist[y] = dist[w] +1, isdiscovered[y] = 1. Here's a code implementing it:

void bfs(){
    std::queue<int> bfslist;
    int isdisc[N] = {0};
    for (int i = 0; i < red.size(); i +=1){
        int a = red[i];
        reddist[a] = 0;
        isdisc[i] = 1;
        for (int j = 0; j < adjlist[a].size(); j +=1){
            int b = adjlist[a][j];
            if ((isred[b] == 1) && (isdisc[b] == 0)){
                bfslist.push(b);
                reddist[b] = 1;
                isdisc[b] = 1;
            }
        }
    }
    while (!bfslist.empty()){
            int a = bfslist.front();
            bfslist.pop();
            for (int i = 0; i < adjlist[a].size(); i +=1){
                int b = adjlist[a][i];
                if ((isred[b] ==1) && (isdisc[b] == 0)){
                    bfslist.push(b);
                    reddist[b] = reddist[a]+1;
                    isdisc[b] = 1;
                }
            }
    }
}

https://pastebin.com/cCYBLvjs

https://mirror.codeforces.com/contest/342/submission/75643716

...