結果
問題 |
No.1950 片道きゃっちぼーる
|
ユーザー |
![]() |
提出日時 | 2025-03-08 20:19:15 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,592 bytes |
コンパイル時間 | 316 ms |
コンパイル使用メモリ | 82,788 KB |
実行使用メモリ | 169,676 KB |
最終ジャッジ日時 | 2025-03-08 20:19:34 |
合計ジャッジ時間 | 18,504 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 WA * 6 |
ソースコード
class UnionFind: def __init__(self, n: int): self.data = [-1] * (n+1) self.nexts = [i for i in range(n+1)] def root(self, a: int) -> int: if self.data[a] < 0: return a self.data[a] = self.root(self.data[a]) return self.data[a] def unite(self, a: int, b: int) -> bool: pa = self.root(a) pb = self.root(b) if pa == pb: return False if self.data[pa] > self.data[pb]: pa, pb = pb, pa self.data[pa] += self.data[pb] # pa を pb をつなげる self.data[pb] = pa self.nexts[pa], self.nexts[pb] = self.nexts[pb], self.nexts[pa] return True def is_same(self, a: int, b: int) -> bool: return self.root(a) == self.root(b) def size(self, a: int) -> int: """a が属する集合のサイズ""" return -self.data[self.root(a)] def group(self, a: int): """a が属する集合""" yield a x = a while self.nexts[x] != a: x = self.nexts[x] yield x N = int(input()) X = list(map(int, input().split())) A = list(map(int, input().split())) x2i = {X[i]: i for i in range(N)} uf = UnionFind(N) bs = [] for i, (x, a) in enumerate(zip(X, A)): bs.append((x+a, i)) bs.append((x-a, i)) for t in [x+a, x-a]: p = x2i.get(t, -1) if p != -1: uf.unite(i, p) dists = [0] * N for t, i in sorted(bs, reverse=True): if dists[i] >= t: continue for j in uf.group(i): dists[j] = max(dists[j], t) for i in range(N): print(dists[i] - X[i])