結果

問題 No.1170 Never Want to Walk
コンテスト
ユーザー Craft Boss
提出日時 2025-10-08 17:52:35
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,994 bytes
コンパイル時間 387 ms
コンパイル使用メモリ 82,820 KB
実行使用メモリ 117,168 KB
最終ジャッジ日時 2025-10-08 17:52:46
合計ジャッジ時間 8,944 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 30 TLE * 1 -- * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import bisect

# Recursion limitを上げて、深い再帰があってもエラーにならないようにする（Union-Findの経路圧縮のため）
# 任意だが、競技プログラミングではよく使われる
# sys.setrecursionlimit(200000)

class StationConnectivity:
    """
    Union-Findデータ構造を使用して駅の連結性を管理するクラス。
    経路圧縮とサイズによる統合（Union by Size）を実装済み。
    """
    def __init__(self, num_station):
        # parent[i] < 0 の場合、iは根ノードで、値はグループのサイズ（負の値）
        self.parent = [-1] * num_station

    def find(self, id):
        """
        要素 id の根（ルート）を O(α(N)) で探す。（経路圧縮あり）
        """
        if self.parent[id] < 0:
            return id
        # 経路圧縮
        self.parent[id] = self.find(self.parent[id])
        return self.parent[id]

    def union(self, xi, A, B):
        """
        駅の座標リスト xi を O(N log N) で処理し、距離 A <= x - upTox <= B の駅を連結する。
        """
        num_station = len(xi)
        for i, x in enumerate(xi):
            # 接続対象の座標の範囲: [x - B, x - A]
            target_low = x - B
            target_high = x - A

            # i番目の駅より手前 (xi[:i]) の範囲で、接続対象のインデックス範囲を特定

            # 接続開始インデックス: target_low 以上の最初の要素 (二分探索)
            # bisect_left(a, x, lo=0, hi=len(a))
            # hi=i とすることで、xi[:i] の範囲で検索
            start_j = bisect.bisect_left(xi, target_low, hi=i) 
            
            # 接続終了インデックス: target_high を超える最初の要素 (二分探索)
            end_j = bisect.bisect_right(xi, target_high, hi=i) 

            # start_j から end_j の範囲内のすべての駅 j に対して Union 操作を行う
            for j in range(start_j, end_j):
                x_root = self.find(i)
                upTox_root = self.find(j)
                
                if x_root != upTox_root:
                    # Union by Size: サイズの大きい木に小さい木を結合する
                    # self.parent[root] はサイズ * (-1)
                    if self.parent[x_root] > self.parent[upTox_root]: 
                        x_root, upTox_root = upTox_root, x_root
                    
                    self.parent[x_root] += self.parent[upTox_root]
                    self.parent[upTox_root] = x_root
    
    def countReachable(self, id):
        """
        要素 id が属するグループのサイズ（連結な駅の数）を返す。
        """
        return self.parent[self.find(id)] * -1
    
        
def main():
    # 1. 高速な入力処理
    # すべての入力を一括で読み込み、空白で分割
    data = sys.stdin.read().split()
    if not data:
        return

    # 変数のパース
    num_station = int(data[0])
    A = int(data[1])
    B = int(data[2])
    
    # xi のパース (残りのデータ)
    # data[3] から num_station 個分が xi のデータ
    xi = [int(x) for x in data[3:3 + num_station]]

    # 2. Union-Findの実行 (O(N log N))
    railway = StationConnectivity(num_station)
    # NOTE: Union-Findの効率的な処理のためには xi はソートされている前提です
    # 課題文のデータはソートされていることが一般的ですが、もしソートされていなければ
    # xi.sort() を行う必要があります。
    railway.union(xi, A, B)

    # 3. 高速な出力処理
    output = []
    for i in range(num_station):
        # 連結な駅の数を出力リストに追加
        output.append(str(railway.countReachable(i)))
    
    # \n で結合し、末尾に改行を加えて一度に出力
    sys.stdout.write('\n'.join(output) + '\n')

if __name__ == "__main__":
    main()
0