結果
問題 | No.2200 Weird Shortest Path |
ユーザー | 👑 Kazun |
提出日時 | 2023-01-28 20:48:23 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 597 ms / 2,000 ms |
コード長 | 3,950 bytes |
コンパイル時間 | 1,364 ms |
コンパイル使用メモリ | 86,960 KB |
実行使用メモリ | 100,168 KB |
最終ジャッジ日時 | 2023-09-11 08:11:11 |
合計ジャッジ時間 | 18,357 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 78 ms
71,060 KB |
testcase_01 | AC | 78 ms
71,096 KB |
testcase_02 | AC | 80 ms
71,064 KB |
testcase_03 | AC | 97 ms
75,584 KB |
testcase_04 | AC | 105 ms
76,520 KB |
testcase_05 | AC | 79 ms
71,372 KB |
testcase_06 | AC | 79 ms
71,376 KB |
testcase_07 | AC | 83 ms
75,656 KB |
testcase_08 | AC | 94 ms
76,528 KB |
testcase_09 | AC | 92 ms
76,476 KB |
testcase_10 | AC | 78 ms
71,072 KB |
testcase_11 | AC | 77 ms
71,300 KB |
testcase_12 | AC | 78 ms
71,064 KB |
testcase_13 | AC | 76 ms
71,040 KB |
testcase_14 | AC | 77 ms
71,228 KB |
testcase_15 | AC | 93 ms
76,540 KB |
testcase_16 | AC | 77 ms
71,328 KB |
testcase_17 | AC | 287 ms
82,328 KB |
testcase_18 | AC | 395 ms
85,104 KB |
testcase_19 | AC | 556 ms
92,880 KB |
testcase_20 | AC | 578 ms
97,832 KB |
testcase_21 | AC | 312 ms
83,388 KB |
testcase_22 | AC | 386 ms
88,972 KB |
testcase_23 | AC | 562 ms
93,328 KB |
testcase_24 | AC | 244 ms
80,216 KB |
testcase_25 | AC | 573 ms
96,436 KB |
testcase_26 | AC | 559 ms
93,172 KB |
testcase_27 | AC | 294 ms
82,656 KB |
testcase_28 | AC | 474 ms
92,644 KB |
testcase_29 | AC | 562 ms
93,144 KB |
testcase_30 | AC | 565 ms
93,048 KB |
testcase_31 | AC | 402 ms
84,948 KB |
testcase_32 | AC | 566 ms
94,148 KB |
testcase_33 | AC | 578 ms
94,400 KB |
testcase_34 | AC | 597 ms
94,428 KB |
testcase_35 | AC | 585 ms
93,668 KB |
testcase_36 | AC | 589 ms
94,068 KB |
testcase_37 | AC | 584 ms
94,176 KB |
testcase_38 | AC | 579 ms
94,524 KB |
testcase_39 | AC | 374 ms
90,640 KB |
testcase_40 | AC | 305 ms
98,032 KB |
testcase_41 | AC | 251 ms
90,528 KB |
testcase_42 | AC | 270 ms
100,168 KB |
testcase_43 | AC | 346 ms
89,440 KB |
testcase_44 | AC | 345 ms
88,972 KB |
testcase_45 | AC | 352 ms
89,236 KB |
ソースコード
class Union_Find(): __slots__=("n","parents","rank","edges","__group_number") def __init__(self,N): """ 0,1,...,N-1 を要素として初期化する. N: 要素数 """ self.n=N self.parents=[-1]*N self.rank=[0]*N self.edges=[0]*N self.__group_number=N def find(self, x): """ 要素 x の属している族を調べる. x: 要素 """ a=x while self.parents[a]>=0: a=self.parents[a] while self.parents[x]>=0: y=self.parents[x] self.parents[x]=a x=y return a def union(self, x, y): """ 要素 x,y を同一視する. [input] x,y: 要素 [output] 元々が非連結 → True 元々が連結 → False """ x=self.find(x) y=self.find(y) if x==y: self.edges[x]+=1 return False if self.rank[x]<self.rank[y]: x,y=y,x self.__group_number-=1 self.edges[x]+=self.edges[y]+1 self.edges[y]=0 self.parents[x]+=self.parents[y] self.parents[y]=x if self.rank[x]==self.rank[y]: self.rank[x]+=1 return True def size(self, x): """ 要素 x の属している族の要素の数. x: 要素 """ return -self.parents[self.find(x)] def same(self, x, y): """ 要素 x,y は同一視されているか? x,y: 要素 """ return self.find(x) == self.find(y) def members(self, x): """ 要素 x が属している族の要素. ※族の要素の個数が欲しいときは size を使うこと!! x: 要素 """ root = self.find(x) return [i for i in range(self.n) if self.find(i) == root] def edge_count(self, x): """ 要素 x が属する族の辺の本数を求める. x: 要素 """ return self.edges[self.find(x)] def is_tree(self, x): """ 要素 x が属する族が木かどうかを判定する. x: 要素 """ return self.size(x)==self.edges[self.find(x)]+1 def tree_count(self): """ 木になっている属の個数を求める. """ return sum(self.is_tree(g) for g in self.representative()) def representative(self): """ 代表元のリスト """ return [i for i, x in enumerate(self.parents) if x < 0] def group_count(self): """ 族の個数 """ return self.__group_number def all_group_members(self): """ 全ての族の出力 """ X={r:[] for r in self.representative()} for k in range(self.n): X[self.find(k)].append(k) return X def group_list(self): """ 各要素が属している族のリストを出力する. """ return [self.find(x) for x in range(self.n)] def refresh(self): for i in range(self.n): _=self.find(i) def __str__(self): return str(self.all_group_members().values())[13:-2] def __repr__(self): return "Union Find : "+str(self) def __getitem__(self,index): return self.find(index) def __setitem__(self,x,y): self.union(x,y) #================================================== def solve(): from operator import itemgetter N,M=map(int,input().split()) a=[0]*M; b=[0]*M; w=[0]*M for j in range(M): a[j],b[j],w[j]=map(int,input().split()) J=sorted(range(M), key=lambda i:w[i]) U=Union_Find(N+1) X=0 for j in J: if not U.same(a[j],b[j]): X+=U.size(a[j])*U.size(b[j])*w[j] U.union(a[j],b[j]) return X #================================================== import sys input=sys.stdin.readline write=sys.stdout.write print(solve())