結果

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

ソースコード

diff # 

import sys
# sys.setrecursionlimit(200000)

class StationConnectivity:
    def __init__(self, num_station):
        # parent[i] < 0 の場合、iは根ノードで、値はグループのサイズ（負の値）
        self.parent = [-1] * num_station
        # rank[i] は木の高さの上限
        self.rank = [0] * 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_sets(self, root1, root2):
        """Union by Rank: ランクの低い木を高い木に結合する"""
        if root1 == root2:
            return False # すでに同じセット

        # ランクの比較
        if self.rank[root1] < self.rank[root2]:
            root1, root2 = root2, root1
        
        # 結合
        self.parent[root2] = root1
        # サイズの更新
        self.parent[root1] += self.parent[root2]

        # ランクが同じ場合にのみランクを増やす
        if self.rank[root1] == self.rank[root2]:
            self.rank[root1] += 1
        return True

    def union(self, xi, A, B):
        """
        スライディングウィンドウ（二重ポインタ）で接続処理を O(N) に改善。
        """
        num_station = len(xi)
        j_start = 0 
        j_end = 0   

        for i in range(num_station):
            x = xi[i]
            root_i = self.find(i) # 接続元のルートを事前に取得

            # 1. j_start を更新
            while j_start < i and x - xi[j_start] > B:
                j_start += 1

            # 2. j_end を更新
            while j_end < i and x - xi[j_end] >= A:
                j_end += 1
            
            # 3. 範囲 [j_start, j_end) の要素に対して Union を実行
            for j in range(j_start, j_end):
                root_j = self.find(j)
                
                if root_i != root_j:
                    # Union 操作の実行（Union by Rankを使用）
                    self.union_sets(root_i, root_j)
                    # root_iが変化した可能性があるため、再度ルートを取得
                    root_i = self.find(root_i) 
                
                # ここが重要: j が root_i と同じグループなら、処理をスキップ

    def countReachable(self, id):
        return self.parent[self.find(id)] * -1
    
        
def main():
    # 高速な入力処理
    data = sys.stdin.read().split()
    if not data:
        return

    num_station = int(data[0])
    A = int(data[1])
    B = int(data[2])
    xi = [int(x) for x in data[3:3 + num_station]]

    # O(N) の Union-Find 実行
    railway = StationConnectivity(num_station)
    railway.union(xi, A, B)

    # 高速な出力処理
    output = []
    for i in range(num_station):
        output.append(str(railway.countReachable(i)))
    
    sys.stdout.write('\n'.join(output) + '\n')

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