結果
問題 |
No.1950 片道きゃっちぼーる
|
ユーザー |
![]() |
提出日時 | 2024-07-15 09:17:38 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 874 bytes |
コンパイル時間 | 351 ms |
コンパイル使用メモリ | 82,412 KB |
実行使用メモリ | 229,476 KB |
最終ジャッジ日時 | 2024-07-15 09:17:44 |
合計ジャッジ時間 | 6,100 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 3 TLE * 1 -- * 19 |
ソースコード
from collections import defaultdict import sys sys.setrecursionlimit(10 ** 6) INF = 1 << 60 N = int(input()) X = list(map(int, input().split())) A = list(map(int, input().split())) x2i = {X[i]: i for i in range(N)} # 逆辺 : 人 i へ到達する人リスト r_adj = defaultdict(list) for i, (x, a) in enumerate(zip(X, A)): for xa in [x+a, x-a]: p = x2i.get(xa, -1) if p != -1: r_adj[p].append(i) # 人 p へ到達できる人は x まで到達できる def dfs(p, used: set): if p in used: return used.add(p) yield p for to in r_adj[p]: yield from dfs(to, used) ans = [-INF] * N # 飛距離が大きい順に確定していく for i, xa in sorted([(i, X[i]+A[i]) for i in range(N)], key=lambda x: x[1], reverse=True): for p in dfs(i, set()): ans[p] = max(ans[p], xa - X[p]) print(*ans, sep='\n')