結果

問題 No.1950 片道きゃっちぼーる
ユーザー norioc
提出日時 2025-03-09 21:04:31
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 862 bytes
コンパイル時間 616 ms
コンパイル使用メモリ 82,232 KB
実行使用メモリ 413,480 KB
最終ジャッジ日時 2025-03-09 21:04:58
合計ジャッジ時間 19,497 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21 TLE * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

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


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

    used = set()
    dfs(i, used)
    for p in used:
        if dists[p] != 0: continue
        dists[p] = x

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