結果
問題 | No.1950 片道きゃっちぼーる |
ユーザー | とりゐ |
提出日時 | 2022-05-20 22:30:56 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,529 ms / 3,000 ms |
コード長 | 1,648 bytes |
コンパイル時間 | 161 ms |
コンパイル使用メモリ | 81,688 KB |
実行使用メモリ | 455,408 KB |
最終ジャッジ日時 | 2023-10-20 13:14:30 |
合計ジャッジ時間 | 14,796 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 41 ms
53,524 KB |
testcase_01 | AC | 40 ms
53,524 KB |
testcase_02 | AC | 38 ms
53,524 KB |
testcase_03 | AC | 494 ms
233,716 KB |
testcase_04 | AC | 989 ms
455,408 KB |
testcase_05 | AC | 87 ms
53,504 KB |
testcase_06 | AC | 768 ms
365,160 KB |
testcase_07 | AC | 289 ms
166,576 KB |
testcase_08 | AC | 314 ms
165,752 KB |
testcase_09 | AC | 819 ms
339,572 KB |
testcase_10 | AC | 428 ms
197,732 KB |
testcase_11 | AC | 394 ms
199,748 KB |
testcase_12 | AC | 420 ms
200,008 KB |
testcase_13 | AC | 587 ms
194,976 KB |
testcase_14 | AC | 435 ms
156,764 KB |
testcase_15 | AC | 1,529 ms
396,028 KB |
testcase_16 | AC | 893 ms
381,572 KB |
testcase_17 | AC | 39 ms
53,504 KB |
testcase_18 | AC | 440 ms
194,512 KB |
testcase_19 | AC | 1,453 ms
384,024 KB |
testcase_20 | AC | 305 ms
166,156 KB |
testcase_21 | AC | 425 ms
169,252 KB |
testcase_22 | AC | 418 ms
166,716 KB |
ソースコード
import sys sys.setrecursionlimit(10**7) def scc(N, G, RG): order = [] used = [0]*N group = [None]*N def dfs(s): used[s] = 1 for t in G[s]: if not used[t]: dfs(t) order.append(s) def rdfs(s, col): group[s] = col used[s] = 1 for t in RG[s]: if not used[t]: rdfs(t, col) for i in range(N): if not used[i]: dfs(i) used = [0]*N label = 0 for s in reversed(order): if not used[s]: rdfs(s, label) label += 1 return label, group # 縮約後のグラフを構築 def construct(N, G, label, group): G0 = [set() for i in range(label)] GP = [[] for i in range(label)] for v in range(N): lbs = group[v] for w in G[v]: lbt = group[w] if lbs == lbt: continue G0[lbs].add(lbt) GP[lbs].append(v) return G0, GP n=int(input()) x=list(map(int,input().split())) a=list(map(int,input().split())) G=[[] for i in range(n)] RG=[[] for i in range(n)] id={} for i in range(n): id[x[i]]=i for i in range(n): xi,ai=x[i],a[i] if xi-ai in id: j=id[xi-ai] G[j].append(i) RG[i].append(j) if xi+ai in id: j=id[xi+ai] G[j].append(i) RG[i].append(j) label,group=scc(n,G,RG) G0,GP=construct(n, G, label, group) mx=[a[i]+x[i] for i in range(n)] mx2=[0]*label for i in range(label): tmp=mx2[i] for j in GP[i]: tmp=max(tmp,mx[j]) for j in GP[i]: mx[j]=tmp for to in G0[i]: mx2[to]=max(tmp,mx2[to]) for i in range(n): print(mx[i]-x[i])