結果
問題 | No.19 ステージの選択 |
ユーザー | ytft |
提出日時 | 2022-11-03 09:45:21 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 76 ms / 5,000 ms |
コード長 | 1,335 bytes |
コンパイル時間 | 286 ms |
コンパイル使用メモリ | 86,740 KB |
実行使用メモリ | 71,552 KB |
最終ジャッジ日時 | 2023-09-24 19:29:37 |
合計ジャッジ時間 | 3,495 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 74 ms
71,496 KB |
testcase_01 | AC | 73 ms
71,312 KB |
testcase_02 | AC | 73 ms
71,180 KB |
testcase_03 | AC | 73 ms
71,372 KB |
testcase_04 | AC | 74 ms
71,184 KB |
testcase_05 | AC | 73 ms
71,316 KB |
testcase_06 | AC | 75 ms
71,372 KB |
testcase_07 | AC | 76 ms
71,424 KB |
testcase_08 | AC | 76 ms
71,380 KB |
testcase_09 | AC | 73 ms
71,376 KB |
testcase_10 | AC | 74 ms
71,484 KB |
testcase_11 | AC | 74 ms
71,424 KB |
testcase_12 | AC | 75 ms
71,412 KB |
testcase_13 | AC | 74 ms
71,472 KB |
testcase_14 | AC | 73 ms
71,460 KB |
testcase_15 | AC | 74 ms
71,488 KB |
testcase_16 | AC | 74 ms
71,424 KB |
testcase_17 | AC | 74 ms
71,268 KB |
testcase_18 | AC | 74 ms
71,316 KB |
testcase_19 | AC | 74 ms
71,052 KB |
testcase_20 | AC | 74 ms
71,456 KB |
testcase_21 | AC | 74 ms
71,504 KB |
testcase_22 | AC | 73 ms
71,552 KB |
testcase_23 | AC | 76 ms
71,396 KB |
ソースコード
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))