Overview

Given \(N\) settlements placed on a plane, this problem asks you to answer \(Q\) queries, where each query specifies a settlement \(C_k\) as the reference point and asks for the sum of Euclidean distances (truncated) from that settlement to all other settlements.

Analysis

Naive Approach

The simplest method is, for each given query \(k\), to compute the distance between settlement \(C_k\) and every other settlement \(j\). In this case, each query takes \(O(N)\) computation time. 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\). In the worst case, the number of computations is approximately \(2000 \times (2 \times 10^5) = 4 \times 10^8\) (400 million), and since it includes heavy operations such as square root calculations, it will not fit within the time limit (typically 2.0 seconds) and will result in TLE (Time Limit Exceeded).

Efficient Approach (Precomputation)

Here, we notice that the number of settlements \(N\) is relatively small (\(N \le 2000\)) compared to the number of queries \(Q\). There are only \(N\) candidates that can serve as the base. Therefore, the approach of “precomputing the answer for every settlement as the base” is effective.

The number of all pairs \((i, j)\) of settlements is \(\frac{N(N-1)}{2}\). When \(N = 2000\), this is approximately \(2 \times 10^6\) (2 million) pairs. Computing the distance for all pairs and accumulating them into the total for each settlement can be done in \(O(N^2)\) time.

With precomputation, each query \(C_k\) can be answered in \(O(1)\) by simply looking up the precomputed array value. This reduces the overall time complexity to \(O(N^2 + Q)\), which comfortably fits within the time limit.

Algorithm

1. Initialization Prepare an array ans (size \(N\), initialized to \(0\)) to store the sum of distances from each settlement \(i\).

2. Precomputation (\(O(N^2)\)) For all pairs of settlements \((i, j)\) (where \(i < j\)), do the following:

   • Compute the squared distance \(dist\_sq = (X_i - X_j)^2 + (Y_i - Y_j)^2\).
   • Compute the floor of its square root \(d = \lfloor \sqrt{dist\_sq} \rfloor\).
   • Add \(d\) to the total for both settlement \(i\) and settlement \(j\) (ans[i] += d, ans[j] += d).

3. Query Processing (\(O(Q)\)) For each query with settlement \(C_k\), directly output the precomputed value ans[C_k].

Complexity

• Time Complexity: \(O(N^2 + Q)\)
  • The precomputation takes \(O(N^2)\) time to compute distances for all pairs of settlements.
  • Each query is answered in \(O(1)\), so the total query processing takes \(O(Q)\) time.
  • When \(N = 2000, Q = 2 \times 10^5\), the total number of computations is approximately \(2.2 \times 10^6\), which runs very fast.
• Space Complexity: \(O(N)\)
  • \(O(N)\) memory is used for the array holding each settlement’s coordinates and the array ans holding the computed answers.

Implementation Notes

• Accurate Integer Square Root Computation (isqrt function) The C++ standard function std::sqrt returns a floating-point number (double), which may produce errors when applying truncation (floor function) due to precision limitations or very large values. To prevent this, the provided code defines an isqrt function. After obtaining an approximate value with std::sqrt, it rigorously searches for the largest integer x satisfying x * x <= n using only integer arithmetic around that approximate value, completely eliminating errors.

• Fast I/O Since the number of queries \(Q\) is as large as \(2 \times 10^5\), the synchronization of C++ standard I/O (cin/cout) is disabled to speed things up.

  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  

  Additionally, "\n" is used instead of std::endl (which is slow because it flushes the buffer) for line breaks, preventing I/O from becoming a bottleneck.

  Source Code

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

// 整数nの平方根の床関数を正確に求める関数
long long isqrt(long long n) {
    if (n <= 0) return 0;
    long long x = sqrt(n);
    while ((x + 1) * (x + 1) <= n) x++;
    while (x * x > n) x--;
    return x;
}

int main() {
    // 入出力の高速化
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, Q;
    if (!(cin >> N >> Q)) return 0;

    vector<long long> X(N), Y(N);
    for (int i = 0; i < N; ++i) {
        cin >> X[i] >> Y[i];
    }

    // 各集落から全集落への距離の切り捨て合計を事前に計算する
    vector<long long> ans(N, 0);
    for (int i = 0; i < N; ++i) {
        for (int j = i + 1; j < N; ++j) {
            long long dx = X[i] - X[j];
            long long dy = Y[i] - Y[j];
            long long dist_sq = dx * dx + dy * dy;
            long long d = isqrt(dist_sq);
            ans[i] += d;
            ans[j] += d;
        }
    }

    // 各クエリに対してO(1)で回答する
    for (int k = 0; k < Q; ++k) {
        int C;
        cin >> C;
        --C; // 0-indexed に変換
        cout << ans[C] << "\n";
    }

    return 0;
}

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