結果
問題 | No.1207 グラフX |
ユーザー |
![]() |
提出日時 | 2020-08-30 14:59:57 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 853 ms / 2,000 ms |
コード長 | 1,719 bytes |
コンパイル時間 | 227 ms |
コンパイル使用メモリ | 82,024 KB |
実行使用メモリ | 202,416 KB |
最終ジャッジ日時 | 2024-11-15 08:27:33 |
合計ジャッジ時間 | 33,102 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 46 |
ソースコード
import sysinput = sys.stdin.readlinefrom operator import itemgettermod = 10**9+7N,M,X=map(int,input().split())E=[tuple(map(int,input().split())) for i in range(M)]E.sort(key=itemgetter(2))# UnionFindGroup = [i for i in range(N+1)] # グループ分けNodes = [1]*(N+1) # 各グループのノードの数def find(x):while Group[x] != x:x=Group[x]return xdef Union(x,y):if find(x) != find(y):if Nodes[find(x)] < Nodes[find(y)]:Nodes[find(y)] += Nodes[find(x)]Nodes[find(x)] = 0Group[find(x)] = find(y)else:Nodes[find(x)] += Nodes[find(y)]Nodes[find(y)] = 0Group[find(y)] = find(x)E2=[]for x,y,z in E:if find(x)!=find(y):E2.append((x,y,z))Union(x,y)EDGE=[[] for i in range(N+1)]D=[0]*(N+1)for x,y,z in E2:EDGE[x].append((y,z))EDGE[y].append((x,z))D[x]+=1D[y]+=1for i in range(1,N+1):if D[i]==1:ROOT=ibreakQUE=[ROOT]Parent=[-1]*(N+1)Score=[-1]*(N+1)Parent[ROOT]=N+1 # ROOTの親を定めておく.TOP_SORT=[] # トポロジカルソートwhile QUE: # トポロジカルソートと同時に親を見つけるx=QUE.pop()TOP_SORT.append(x)for to,sc in EDGE[x]:if Parent[to]==-1:Score[to]=scParent[to]=xQUE.append(to)Children=[1]*(N+1)for x in TOP_SORT[1:][::-1]: #(自分を含む)子ノードの数を調べるChildren[Parent[x]]+=Children[x]ANS=0for i in range(1,N+1):if i==ROOT:continuec=Children[i]ANS=ANS+c*(N-c)*pow(X,Score[i],mod)ANS%=modprint(ANS)