結果
問題 | No.1170 Never Want to Walk |
ユーザー | cmy |
提出日時 | 2022-05-23 01:10:46 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 268 ms / 2,000 ms |
コード長 | 2,873 bytes |
コンパイル時間 | 221 ms |
コンパイル使用メモリ | 81,876 KB |
実行使用メモリ | 109,108 KB |
最終ジャッジ日時 | 2023-10-20 17:24:49 |
合計ジャッジ時間 | 7,141 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 34 ms
53,604 KB |
testcase_01 | AC | 34 ms
53,604 KB |
testcase_02 | AC | 38 ms
53,604 KB |
testcase_03 | AC | 34 ms
53,604 KB |
testcase_04 | AC | 34 ms
53,604 KB |
testcase_05 | AC | 35 ms
53,604 KB |
testcase_06 | AC | 34 ms
53,604 KB |
testcase_07 | AC | 35 ms
53,604 KB |
testcase_08 | AC | 36 ms
53,604 KB |
testcase_09 | AC | 35 ms
53,604 KB |
testcase_10 | AC | 35 ms
53,604 KB |
testcase_11 | AC | 34 ms
53,604 KB |
testcase_12 | AC | 55 ms
68,012 KB |
testcase_13 | AC | 60 ms
70,376 KB |
testcase_14 | AC | 66 ms
72,600 KB |
testcase_15 | AC | 58 ms
68,012 KB |
testcase_16 | AC | 58 ms
68,012 KB |
testcase_17 | AC | 65 ms
72,600 KB |
testcase_18 | AC | 57 ms
68,024 KB |
testcase_19 | AC | 55 ms
68,008 KB |
testcase_20 | AC | 65 ms
72,600 KB |
testcase_21 | AC | 55 ms
68,012 KB |
testcase_22 | AC | 63 ms
72,676 KB |
testcase_23 | AC | 69 ms
73,060 KB |
testcase_24 | AC | 58 ms
68,536 KB |
testcase_25 | AC | 53 ms
68,528 KB |
testcase_26 | AC | 71 ms
73,520 KB |
testcase_27 | AC | 231 ms
108,328 KB |
testcase_28 | AC | 213 ms
108,176 KB |
testcase_29 | AC | 268 ms
108,992 KB |
testcase_30 | AC | 226 ms
108,412 KB |
testcase_31 | AC | 238 ms
108,336 KB |
testcase_32 | AC | 195 ms
109,040 KB |
testcase_33 | AC | 198 ms
107,952 KB |
testcase_34 | AC | 188 ms
108,528 KB |
testcase_35 | AC | 197 ms
109,108 KB |
testcase_36 | AC | 190 ms
108,652 KB |
testcase_37 | AC | 196 ms
108,816 KB |
testcase_38 | AC | 193 ms
108,800 KB |
ソースコード
from bisect import bisect_left, bisect_right class UnionFind: """Union Find 木 Args: n (int): 要素数 """ def __init__(self, n: int): # 独立した n 個のノードで初期化、根の場合は絶対値がノード数 self.n = n self._parent = [-1] * n def __str__(self): return str(self.groups()) def root(self, x: int) -> int: """根の探索 Args: x (int): ノードの index Returns: int: 根の index """ if self._parent[x] < 0: return x else: # 縮約 self._parent[x] = self.root(self._parent[x]) return self._parent[x] def unite(self, x: int, y: int) -> None: """ノードの結合 Args: x (int): ノードの index y (int): ノードの index """ px = self.root(x) py = self.root(y) if px == py: return # ノード数が多い方を px、少ない方を py if self._parent[px] > self._parent[py]: px, py = py, px # py -> px self._parent[px] += self._parent[py] self._parent[py] = px def is_same(self, x: int, y: int) -> bool: """グループ 一致判定 Args: x (int): ノードの index y (int): ノードの index Returns: bool: 一致 / 不一致 """ return self.root(x) == self.root(y) def size(self, x: int) -> int: """グループ内 ノード数 Args: x (int): ノードの index Returns: int: ノード数 """ return -self._parent[self.root(x)] def roots(self) -> int: """全ての根の index を返す Yields: int: ノードの index """ for idx, rnk in enumerate(self._parent): if rnk < 0: yield idx def sizes(self) -> int: """全ての木のサイズを返す Yields: int: 木のサイズ """ for r in self.roots(): yield self.size(r) def groups(self) -> list: """全ての木を返す Yields: list: 木の一覧 """ tmp = {} for i in range(self.n): j = self.root(i) tmp[j] = tmp.get(j, []) tmp[j].append(i) for nodes in tmp.values(): yield nodes n, a, b = map(int, input().split()) *x, = map(int, input().split()) lo = 0 uf = UnionFind(n) for i in range(n-1): xi = x[i] js = bisect_left(x, xi+a, lo=lo) je = bisect_right(x, xi+b, lo=lo) - 1 if js > je: continue for j in range(js, je+1): uf.unite(i, j) lo = je - 1 for i in range(n): print(uf.size(i))