結果
問題 |
No.1950 片道きゃっちぼーる
|
ユーザー |
![]() |
提出日時 | 2025-03-09 21:15:38 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,613 ms / 3,000 ms |
コード長 | 884 bytes |
コンパイル時間 | 638 ms |
コンパイル使用メモリ | 82,284 KB |
実行使用メモリ | 404,040 KB |
最終ジャッジ日時 | 2025-03-09 21:15:58 |
合計ジャッジ時間 | 17,469 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 23 |
ソースコード
from collections import defaultdict import sys sys.setrecursionlimit(10 ** 6) N = int(input()) X = list(map(int, input().split())) A = list(map(int, input().split())) x2i = {X[i]: i for i in range(N)} bs = [] r_adj = defaultdict(list) # r_adj[i] : 人 i へボールを渡せる人リスト for i, (x, a) in enumerate(zip(X, A)): bs.append((x+a, i)) for x2 in [x+a, x-a]: q = x2i.get(x2, -1) if q != -1: r_adj[q].append(i) # 人 p へ到達可能な人を全て求める def dfs(p, used, dists): if p in used: return used.add(p) for to in r_adj[p]: if dists[to] != 0: continue dfs(to, used, dists) dists = [0] * N for x, i in sorted(bs, reverse=True): if dists[i] != 0: continue used = set() dfs(i, used, dists) for p in used: dists[p] = x for i in range(N): print(dists[i] - X[i])