結果

問題 No.1950 片道きゃっちぼーる
コンテスト
ユーザー norioc
提出日時 2025-03-09 21:13:18
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,409 ms / 3,000 ms
コード長 933 bytes
コンパイル時間 928 ms
コンパイル使用メモリ 82,388 KB
実行使用メモリ 410,064 KB
最終ジャッジ日時 2025-03-09 21:13:39
合計ジャッジ時間 15,780 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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, excludes):
    if p in used: return
    used.add(p)

    for to in r_adj[p]:
        if to in excludes: continue
        dfs(to, used, excludes)


dists = [0] * N
exclues = set()
for x, i in sorted(bs, reverse=True):
    if dists[i] != 0: continue

    used = set()
    dfs(i, used, exclues)
    exclues.update(used)
    for p in used:
        dists[p] = x

for i in range(N):
    print(dists[i] - X[i])
0