結果
問題 |
No.1170 Never Want to Walk
|
ユーザー |
|
提出日時 | 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 |
ソースコード
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()