Fundamental Idea

Consider the following undirected graph \(G\).

• It has \(K\) vertices corresponding to the points with houses.
• For all \(i\) and \(j(1 \leq i \lt j \leq K)\), there exists an edge between Vertices \(i\) and \(j\), whose cost is the distance from Point \(i\) to Point \(j\).

The answer for the original problem is equal to that on \(G\), so the following solution is valid (in that it outputs correct answers).

• Sort the edges of \(G\) in the increasing order. When processing the \(i\)-th query, add to DSU (Disjoint Set Union) edges of costs no more than \(t_i\) that are not added yet. Then, check if Vertices \(x_i\) and \(y_i\) belongs to the same connected component.

However, we cannot handle \(\mathrm{O}(K^2)\) number of edges, so we have to improve it.

Reducing Edges

Let \(T\) be a minimum spanning tree of \(G\). In fact, the answer on \(T\) corresponds to that on \(G\).

Proof

The negation of the proposition above is as follows.

• There exist vertices \(u\) and \(v\) such that the cost on \(G\) from \(u\) to \(v\) is strictly less than the cost on \(T\) from \(u\) to \(v\).
  

If it is true, then the path on \(T\) between \(u\) and \(v\) has an edge with larger cost than the edge on \(G\) between \(u\) and \(v\). However, if such an edge, by removing it and adding the edge between \(u\) and \(v\) instead, we can construct a spanning tree with smaller cost, which contradicts to the assumption that \(T\) is a minimum spanning tree. Therefore, the answer on \(T\) is equal to that on \(G\).

This is a significant reduction because \(T\) has only \((K-1)\) edges.

Finding the minimum spanning tree

Among various algorithms to find a minimum spanning tree, Kursukal’s algorithm requires actually finding the \(\mathrm{O}(K^2)\) number of edges, and Prim’s algorithm requires executing Dijkstra’s algorithm in order to find the edge with minimum cost every time an edge is added, both of which are difficult to apply to this problem. On the other hand, Borůvka’s algorithm allows us to find it in a total of \(\mathrm{O}(M(\log K)^2)\) time.
Specifically, we construct the minimum spanning tree \(T\) in the following steps.

• Initialize \(T\) as a \(K\)-vertex and \(0\)-edge graph

• Repeat the following until \(T\) becomes a spanning tree

  • For each connected component, find the edge with minimum cost which connects that connected component and different connected component. Add to \(T\) the sum set of the found edges.

Finding for each connected component the edge that connects different connected component can be done in \(\mathrm{O}(M\log K)\) in the same way as the solution of ABC245-G. Since the loop is repeated \(\mathrm{O}(\log K)\) times (considering the fact that each connected component after a single iteration contains two or more connected components before the iteration), this algorithm indeed works in a total of \(\mathrm{O}(M(\log K)^2)\) time.

Another solution

Here is another solution which an admin come up with.
Let \(d_i\) be the minimum distance from each Point \(i\) to the nearest house. Also, for the \(i\)-th road, let \(c_i'=c_i+d_{a_i}+d_{b_i}\).
Here, the following fact holds.

• The answer for the query is Yes if and only if one can travel from \(x\) to \(y\) only using roads satisfying \(c_i' \leq t\).
  

Proof

First, since \(c_i'\) represents the minimum cost of path from a house to another house using the \(i\)-th house, if it is unable to travel only using roads satisfying \(c_i' \leq t\), then the answer is No.
On the other hand, suppose that one can travel from \(x\) to \(y\) only using roads satisfying \(c_i' \leq t\). Consider the following path.

• Denoting by \(p_1,\ldots ,p_k\) the points on a path from \(x\) to \(y\), consider the path \(p_1, (\text{Nearest house from }p_1), p_1, p_2, (\text{Nearest house from }p_2), p_2, \ldots, p_k \)

Since the length of \((\text{Nearest house from }p_i), p_i, p_{i+1}, (\text{Nearest house from }p_{i+1})\) is equal to \(c'\) of the road connecting \(p_i\) and \(p_{i+1}\), the time required to travel from a house to the next house in this path is no more than \(t\). Therefore, the answer for this case is Yes.

The solution is different from the first solution. The values of \(d_i\) can be found by Dijkstra’s algorithm from sources \(1,\ldots, K\) in a total of \(\mathrm{O}(M\log N)\) time. When answering the query, sort the values of \(c'\), and as \(t\) increases, add the roads satisfying \(c' \leq t\) to DSU and check if \(x\) and \(y\) are connected.