結果
問題 | No.19 ステージの選択 |
ユーザー |
![]() |
提出日時 | 2022-11-03 09:45:21 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 36 ms / 5,000 ms |
コード長 | 1,335 bytes |
コンパイル時間 | 232 ms |
コンパイル使用メモリ | 82,376 KB |
実行使用メモリ | 54,580 KB |
最終ジャッジ日時 | 2024-07-17 20:08:44 |
合計ジャッジ時間 | 1,948 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 24 |
ソースコード
import sys input=lambda:sys.stdin.readline().rstrip() class unionFind: def __init__(self,N): self.N=N self.parent=[-1 for i in range(N)] self.size=[1 for i in range(N)] def find(self,x): path=[x] while self.parent[path[-1]]!=-1: path.append(self.parent[path[-1]]) for i in path[:-1]: self.parent[i]=path[-1] return path[-1] def unite(self,x,y): roots=sorted([self.find(x),self.find(y)],key=lambda _:self.parent[_]) if roots[0]!=roots[1]: self.parent[roots[0]]=roots[1] self.size[roots[1]]+=self.size[roots[0]] N=int(input()) diff=[0 for i in range(N)] nex=[0 for i in range(N)] prev=[0 for i in range(N)] rem=[1 for i in range(N)] ans=0 m={} u=unionFind(N) for i in range(N): diff[i],prev[i]=map(int,input().split()) prev[i]-=1 nex[prev[i]]+=1 u.unite(i,prev[i]) erase=[] for i in range(N): if nex[i]==0: erase.append(i) while len(erase): temp=erase[-1] erase.pop() if rem[temp]==0: continue ans+=diff[temp]/2 nex[prev[temp]]-=1 rem[temp]=0 if nex[prev[temp]]==0: erase.append(prev[temp]) for i in range(N): if rem[i]: ans+=diff[i]/2 if not u.find(i) in m: m[u.find(i)]=float('inf') m[u.find(i)]=min(m[u.find(i)],diff[i]) for i in m: ans+=m[i]/2 print('{:.1f}'.format(ans))