結果
問題 | No.1207 グラフX |
ユーザー |
|
提出日時 | 2020-08-30 13:44:41 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,414 ms / 2,000 ms |
コード長 | 1,685 bytes |
コンパイル時間 | 271 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 311,248 KB |
最終ジャッジ日時 | 2024-11-15 06:56:28 |
合計ジャッジ時間 | 29,615 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 46 |
ソースコード
class UnionFindVerSize():def __init__(self, N):self._parent = [n for n in range(0, N)]self._size = [1] * Ndef find_root(self, x):if self._parent[x] == x: return xself._parent[x] = self.find_root(self._parent[x])return self._parent[x]def unite(self, x, y):gx = self.find_root(x)gy = self.find_root(y)if gx == gy: returnif self._size[gx] < self._size[gy]:self._parent[gx] = gyself._size[gy] += self._size[gx]else:self._parent[gy] = gxself._size[gx] += self._size[gy]def get_size(self, x):return self._size[self.find_root(x)]def is_same_group(self, x, y):return self.find_root(x) == self.find_root(y)def calc_group_num(self):N = len(self._parent)ans = 0for i in range(N):if self.find_root(i) == i:ans += 1return ansimport sysfrom collections import dequeinput=sys.stdin.readlinesys.setrecursionlimit(2*10**5)N,M,X=map(int,input().split())uf=UnionFindVerSize(N)ans=0mod=10**9+7MST = []edge = [[] for i in range(N)]for i in range(M):x,y,z=map(int,input().split())x-=1y-=1if not uf.is_same_group(x,y):uf.unite(x,y)edge[x].append((y,z))edge[y].append((x,z))size=[1 for i in range(N)]def dfs(v,pv):for nv,c in edge[v]:if nv!=pv:dfs(nv,v)size[v]+=size[nv]dfs(0,-1)res=0for u in range(N):for v,c in edge[u]:if size[u]<size[v]:res+=pow(X,c,mod)*size[u]*(N-size[u])res%=modprint(res)