結果
問題 | No.1767 BLUE to RED |
ユーザー |
|
提出日時 | 2024-07-05 09:40:48 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,380 ms / 2,000 ms |
コード長 | 878 bytes |
コンパイル時間 | 142 ms |
コンパイル使用メモリ | 81,832 KB |
実行使用メモリ | 210,520 KB |
最終ジャッジ日時 | 2024-07-05 09:41:11 |
合計ジャッジ時間 | 19,891 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
import sysfrom heapq import heappush, heappop, heapifyinput = sys.stdin.buffer.readlineN, M = map(int, input().split())A = list(map(int, input().split()))B = list(map(int, input().split()))G = [[] for _ in range(N + M + 1)]S = [(x, 1) for x in A] + [(x, 0) for x in B]S.sort()for i, (x, c) in enumerate(S, 1):if c:G[0].append((i, 0))G[i].append((0, 0))for i in range(1, N + M):G[i].append((i + 1, S[i][0] - S[i - 1][0]))G[i + 1].append((i, S[i][0] - S[i - 1][0]))# https://tjkendev.github.io/procon-library/python/graph/min_st_prim.htmlused = [0] * (N + M + 1)que = [(c, w) for w, c in G[0]]used[0] = 1heapify(que)ans = 0while que:cv, v = heappop(que)if used[v]:continueused[v] = 1ans += cvfor w, c in G[v]:if used[w]:continueheappush(que, (c, w))print(ans)