結果

問題 No.1950 片道きゃっちぼーる
コンテスト
ユーザー SidewaysOwl
提出日時 2022-05-21 00:29:41
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,200 bytes
コンパイル時間 199 ms
コンパイル使用メモリ 82,444 KB
実行使用メモリ 168,716 KB
最終ジャッジ日時 2024-09-20 10:46:25
合計ジャッジ時間 7,785 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 19 WA * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

n = int(input())
x = list(map(int,input().split()))
a = list(map(int,input().split()))
xx = {}
for i in range(n):
    xx[x[i]] = i
from collections import deque
def dfs():
    vis = [-1] * n
    vis_max_idx = [-1] * n
    for i in range(n):
        if vis[i] == -1:
            q = deque([(x[i],x[i])])
            dist_max = 0
            while q:
                node,dist = q.popleft()
                idx = xx[node]
                dist = node + a[idx]
                dist_max = max(dist_max ,dist)
                vis[idx] = i
                if a[idx] + node in xx:
                    if vis[xx[a[idx] + node]] != -1:
                        dist_max = max(dist_max, vis_max_idx[vis[xx[a[idx] + node]]])
                    else:
                        q.append((a[idx] + node,dist))
                if node - a[idx]  in xx:
                    if vis[xx[node - a[idx]]] != -1:
                        dist_max = max(dist_max , vis_max_idx[vis[xx[node - a[idx] ]]])
                    else:
                        q.append((node - a[idx] ,dist))
            vis_max_idx[i] = dist_max
    return vis,vis_max_idx
vis,vis_max_idx = dfs()
for i in range(n):
    print(vis_max_idx[vis[i]]-x[i])
0