Overview

From \(N\) settlements, you choose one settlement as a base and calculate the sum of the “floored Euclidean distances” from that base to all settlements. Since there are \(Q\) queries (considerations), efficient computation is required.

Analysis

1. Naive Solution and Its Limitations

If we calculate the distance to all \(N\) settlements for each query, the total time complexity becomes \(O(Q \times N)\). Given the constraints of this problem, \(N \le 2000, Q \le 2 \times 10^5\), the number of computations reaches a maximum of \(2 \times 10^5 \times 2000 = 4 \times 10^8\). Under typical time limits (around 2 seconds), especially in Python, this computational load cannot be handled and will result in a Time Limit Exceeded (TLE) verdict.

2. Key Insight: The Number of Base Candidates Is Limited

The base is always chosen from one of the \(N\) settlements. In other words, the number of patterns for “which settlement to use as a base” is at most \(N\). Since the same settlement may be specified multiple times across queries, we can eliminate redundant calculations by reusing previously computed results.

3. Speedup Through Precomputation

Before processing queries, we precompute the total distance for each settlement when used as a base. - Perform calculations for each candidate base settlement’s coordinates. - Store the computed results in a dictionary (associative array) or similar structure. - For each query, retrieve the stored result in \(O(1)\).

This reduces the overall time complexity to \(O(N^2 + Q)\). Since \(2000^2 + 2 \times 10^5 \approx 4.2 \times 10^6\), this is well within the time limit.

Algorithm

1. Data Aggregation: When multiple settlements share the same coordinates, grouping and counting them can further improve efficiency. Count the number of settlements per coordinate \((X, Y)\) using Counter or similar.
2. Extraction of Unique Base Coordinates: Extract, without duplicates, the coordinates of settlements specified as bases across all queries.
3. Distance Sum Calculation (Main Processing): For each extracted base coordinate \((X_{base}, Y_{base})\), compute the total distance as follows:
   • For every settlement coordinate \((X_j, Y_j)\), calculate the Euclidean distance \(d = \sqrt{(X_{base} - X_j)^2 + (Y_{base} - Y_j)^2}\).
   • Compute \(\lfloor d \rfloor\), multiply it by the number of settlements at that coordinate, and add it to the total.
   • Store the computed total in a dictionary with the base coordinates as the key.
4. Answering Queries: For each query, determine the coordinates of the given settlement number \(C_k\), look up the precomputed value from the dictionary, and output it.

Complexity

• Time Complexity: \(O(N^2 + Q)\)
  • Coordinate aggregation takes \(O(N)\).
  • In precomputation, computing distances between up to \(N\) base candidates and \(N\) settlements takes \(O(N^2)\).
  • Answering queries takes \(O(Q)\).
  • In practice, when coordinates have duplicates, precomputation becomes \(O((\text{number of distinct coordinates})^2)\), which is even faster.
• Space Complexity: \(O(N + Q)\)
  • Required for storing coordinate data, aggregated data, and query results.

Implementation Notes

• Using Integer Square Root: For computing \(\lfloor \sqrt{x} \rfloor\), using Python’s math.isqrt(x) allows obtaining the integer part quickly while avoiding floating-point precision issues.

• Fast I/O: Since \(Q\) is large, using bulk reading with sys.stdin.read().split() and bulk output with sys.stdout.write() eliminates I/O bottlenecks.

• Coordinate-Based Management: By managing computation results using “coordinates” as keys rather than settlement numbers, calculations can be skipped when different settlement numbers share the same coordinates.

  Source Code

import sys
import math
from collections import Counter

def solve():
    """
    救急ヘリコプターの配置問題を解く関数。
    
    N個の集落の座標を読み取り、Q個のクエリ（基地を設置する集落番号）に対して、
    基地から全集落へのユークリッド距離の切り捨ての合計を求める。
    計算量は O(D_B * D + Q) であり、ここで D は集落の異なる座標の数、
    D_B はクエリで指定された集落の異なる座標の数。
    最悪の場合でも O(N^2 + Q) となり、制約下で十分高速に動作する。
    """
    
    # 標準入力から全データを一括で読み込み、スペース区切りで分割する
    try:
        input_data = sys.stdin.read().split()
    except EOFError:
        return
    
    if not input_data:
        return
    
    # イテレータを使用してデータを順番に取得する
    it = iter(input_data)
    try:
        N = int(next(it))
        Q = int(next(it))
    except StopIteration:
        return
    
    # 全集落の座標をリストに格納する
    all_coords = []
    for _ in range(N):
        try:
            x = int(next(it))
            y = int(next(it))
            all_coords.append((x, y))
        except StopIteration:
            break
    
    # 各検討（クエリ）における基地の設置先集落番号を読み込む（0-indexedに変換）
    query_indices = []
    for _ in range(Q):
        try:
            query_indices.append(int(next(it)) - 1)
        except StopIteration:
            break
            
    # 集落の座標ごとの頻度をカウントする（同じ座標に複数の集落がある場合をまとめる）
    counts = Counter(all_coords)
    # 異なる座標、およびその座標にある集落の数をリスト化する
    distinct_info = [(x, y, count) for (x, y), count in counts.items()]
    
    # クエリで指定された集落のうち、ユニークな座標のセットを作成する
    # これにより、同じ座標にある集落を基地とする検討を一度に済ませる
    unique_query_coords = {all_coords[idx] for idx in query_indices}
    
    # 各ユニークな座標を基地とした時の合計距離を格納する辞書
    base_results = {}
    _isqrt = math.isqrt  # 整数平方根（切り捨て）関数
    
    # 各ユニークな基地座標に対して、全集落への距離の合計を計算する
    for xi, yi in unique_query_coords:
        total = 0
        for xj, yj, count_j in distinct_info:
            # ユークリッド距離の二乗を計算
            dx = xi - xj
            dy = yi - yj
            dist_sq = dx * dx + dy * dy
            # 切り捨てられたユークリッド距離を求め、その座標にある集落の数を掛ける
            total += _isqrt(dist_sq) * count_j
        base_results[(xi, yi)] = total
        
    # 各クエリの設置先集落の座標に基づき、計算済みの結果を紐付ける
    # 文字列のリストとして保持し、最後に一括で出力する
    output = [str(base_results[all_coords[idx]]) for idx in query_indices]
    
    # 全ての結果を改行で繋いで標準出力に書き出す
    sys.stdout.write('\n'.join(output) + '\n')

if __name__ == '__main__':
    solve()

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