結果
問題 |
No.860 買い物
|
ユーザー |
![]() |
提出日時 | 2025-08-14 12:42:21 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 857 ms / 1,000 ms |
コード長 | 923 bytes |
コンパイル時間 | 430 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 123,904 KB |
最終ジャッジ日時 | 2025-08-14 12:42:32 |
合計ジャッジ時間 | 10,483 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 15 |
ソースコード
import sys input = sys.stdin.readline N=int(input()) PR=[tuple(map(int,input().split())) for i in range(N)] EDGE=[] ANS=0 for i in range(N): x,y=PR[i] ANS+=x EDGE.append((x,0,i+1)) if i>=1: EDGE.append((y,i,i+1)) # UnionFind Group = [i for i in range(2*N+1)] # グループ分け Nodes = [1]*(2*N+1) # 各グループのノードの数 def find(x): while Group[x] != x: x=Group[x] return x def Union(x,y): if find(x) != find(y): if Nodes[find(x)] < Nodes[find(y)]: Nodes[find(y)] += Nodes[find(x)] Nodes[find(x)] = 0 Group[find(x)] = find(y) else: Nodes[find(x)] += Nodes[find(y)] Nodes[find(y)] = 0 Group[find(y)] = find(x) EDGE.sort() for w,x,y in EDGE: if find(x)==find(y): continue else: ANS+=w Union(x,y) print(ANS)