Overview

This problem asks you to answer \(Q\) queries, where each query requires computing the sum of “floored Euclidean distances” from \(N\) settlements on a plane to a specified settlement \(C_k\). Since computing this for each query individually would be too slow, we precompute the distances between all pairs of settlements, allowing each query to be answered in \(O(1)\).

Analysis

Naive Approach and Its Limitations

The most straightforward method is, for each query \(C_k\), to compute the distance \(\lfloor \sqrt{(X_{C_k} - X_j)^2 + (Y_{C_k} - Y_j)^2} \rfloor\) to every other settlement \(j\) and sum them up. In this case, each query requires \(O(N)\) computation. Since there are \(Q\) queries, the overall time complexity is \(O(NQ)\).

Looking at the constraints, \(N \le 2000\) and \(Q \le 2 \times 10^5\), so in the worst case the number of operations is: $\(N \times Q = 2000 \times (2 \times 10^5) = 4 \times 10^8\)$ which would result in Time Limit Exceeded (TLE) within the typical time limit (2 seconds).

Key to Optimization: Query Independence and Precomputation

Here, each query asks for “the sum of distances when a base is placed at settlement \(C_k\).” This value does not depend on the order of queries or the content of other queries — it is uniquely determined by the arrangement of settlements alone. Additionally, the number of settlements \(N\) is at most \(2000\), which is relatively small.

Therefore, we consider precomputing the sum of distances for every settlement \(i\) \((1 \leq i \leq N)\) when the base is placed at \(i\).

The total number of pairs \((i, j)\) of settlements is \(\frac{N(N-1)}{2}\). When \(N = 2000\), this is: $\(\frac{2000 \times 1999}{2} \approx 2 \times 10^6\)$ which is a scale that a computer can handle in an instant.

The distance between settlement \(i\) and settlement \(j\) is the same whether the base is placed at \(i\) or at \(j\) (symmetry: \(dist(i, j) = dist(j, i)\)), so the result of a single distance computation can be added to the totals for both settlements. This reduces redundant computations by half.

Algorithm

1. Array Preparation: Prepare an array ans of length \(N\) to store the sum of distances for each settlement \(i\), initialized to \(0\).

2. Precomputation for All Pairs: Using a double loop, for all pairs of settlements \((i, j)\) (where \(i < j\)), do the following:

   • Compute the Euclidean distance \(d = \lfloor \sqrt{(X_i - X_j)^2 + (Y_i - Y_j)^2} \rfloor\) between settlement \(i\) and settlement \(j\).
   • Add \(d\) to both ans[i] and ans[j].

3. Answering Queries: For each query \(C_k\), retrieve ans[C_k - 1] from the precomputed array and output it (adjusting for 0-indexed).

Complexity

• Time Complexity: \(O(N^2 + Q)\)

  • The precomputation takes \(O(N^2)\) time to compute distances for all pairs.
  • Each query is answered in \(O(1)\), so processing all \(Q\) queries takes \(O(Q)\) time.
  • When \(N \le 2000, Q \le 2 \times 10^5\), the total number of operations is \(2 \times 10^6 + 2 \times 10^5 \approx 2.2 \times 10^6\), which comfortably fits within the time limit.

• Space Complexity: \(O(N + Q)\)

  • \(O(N)\) memory for the array holding each settlement’s coordinates, \(O(N)\) for the array holding precomputed results, and \(O(Q)\) for the array holding query outputs.

Implementation Notes

• Fast I/O: In Python, when handling large amounts of input/output such as \(Q = 2 \times 10^5\), naively repeating input() and print() can make I/O itself a bottleneck. By reading all input at once with sys.stdin.read and writing all output at once with sys.stdout.write, execution time can be significantly reduced.

• Flooring the Square Root: \(\lfloor \sqrt{x} \rfloor\) can be computed concisely and efficiently in Python using int(math.sqrt(x)).

  Source Code

import math
import sys


def solve():
    # すべての入力を高速に読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    N = int(input_data[0])
    Q = int(input_data[1])

    X = [0] * N
    Y = [0] * N
    idx = 2
    for i in range(N):
        X[i] = int(input_data[idx])
        Y[i] = int(input_data[idx + 1])
        idx += 2

    # 各集落から他のすべての集落への切り捨て距離の合計を前計算する
    # 対称性 (dist(i, j) == dist(j, i)) を利用してループ回数を半分にする
    ans = [0] * N
    sqrt = math.sqrt

    for i in range(N):
        xi = X[i]
        yi = Y[i]
        for j in range(i + 1, N):
            dx = xi - X[j]
            dy = yi - Y[j]
            d = int(sqrt(dx * dx + dy * dy))
            ans[i] += d
            ans[j] += d

    # 各クエリに対して、前計算した結果を O(1) で取得して出力する
    out = []
    for _ in range(Q):
        c = int(input_data[idx]) - 1
        idx += 1
        out.append(str(ans[c]))

    sys.stdout.write("\n".join(out) + "\n")


if __name__ == "__main__":
    solve()

This editorial was generated by gemini-3.5-flash-thinking.