結果

問題 No.1950 片道きゃっちぼーる
ユーザー 👑 H20H20
提出日時 2022-04-08 18:40:49
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,441 ms / 3,000 ms
コード長 727 bytes
コンパイル時間 370 ms
コンパイル使用メモリ 87,128 KB
実行使用メモリ 414,348 KB
最終ジャッジ日時 2023-08-23 06:12:50
合計ジャッジ時間 17,946 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 92 ms
71,696 KB
testcase_01 AC 94 ms
71,396 KB
testcase_02 AC 91 ms
71,724 KB
testcase_03 AC 1,103 ms
402,228 KB
testcase_04 AC 1,381 ms
414,348 KB
testcase_05 AC 99 ms
71,788 KB
testcase_06 AC 789 ms
379,056 KB
testcase_07 AC 478 ms
227,372 KB
testcase_08 AC 914 ms
230,380 KB
testcase_09 AC 938 ms
294,052 KB
testcase_10 AC 626 ms
196,868 KB
testcase_11 AC 466 ms
191,248 KB
testcase_12 AC 556 ms
200,352 KB
testcase_13 AC 529 ms
172,608 KB
testcase_14 AC 530 ms
170,244 KB
testcase_15 AC 1,441 ms
361,852 KB
testcase_16 AC 835 ms
308,732 KB
testcase_17 AC 92 ms
71,688 KB
testcase_18 AC 711 ms
215,716 KB
testcase_19 AC 1,316 ms
306,876 KB
testcase_20 AC 470 ms
191,248 KB
testcase_21 AC 465 ms
171,500 KB
testcase_22 AC 469 ms
171,320 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import collections
import sys
sys.setrecursionlimit(10**6)

N = int(input())
X = list(map(int, input().split())) 
A = list(map(int, input().split()))
if 1<=N<=2*10**5 and 1<=min(A) and max(A)<=10**9 and 0<=min(X) and max(X)<=10**9 and len(set(X))==N and X == sorted(X):
    L = collections.defaultdict(list)
    T = collections.defaultdict(int)
    G = []
    for i in range(N):
        G.append(X[i]+A[i])
        L[X[i]+A[i]].append(X[i])
        L[X[i]-A[i]].append(X[i])
    G.sort(reverse=True)
    def dfs(x,v):
        for l in L[x]:
            if T[l]==0:
                T[l]=v
                dfs(l,v)
    for g in G:
        if T[g]==0:
            T[g]=g
            dfs(g,g)
    for x in X:
        print(T[x]-x)
0