結果

問題 No.1207 グラフX
ユーザー shotoyooshotoyoo
提出日時 2020-08-30 14:44:47
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,373 ms / 2,000 ms
コード長 1,556 bytes
コンパイル時間 302 ms
コンパイル使用メモリ 82,760 KB
実行使用メモリ 347,752 KB
最終ジャッジ日時 2024-11-15 07:53:30
合計ジャッジ時間 35,212 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 764 ms
166,980 KB
testcase_01 AC 757 ms
166,640 KB
testcase_02 AC 759 ms
166,648 KB
testcase_03 AC 764 ms
166,996 KB
testcase_04 AC 769 ms
166,484 KB
testcase_05 AC 1,341 ms
346,480 KB
testcase_06 AC 1,322 ms
346,668 KB
testcase_07 AC 1,316 ms
347,404 KB
testcase_08 AC 660 ms
144,624 KB
testcase_09 AC 719 ms
151,928 KB
testcase_10 AC 1,373 ms
317,276 KB
testcase_11 AC 1,363 ms
347,752 KB
testcase_12 AC 697 ms
145,712 KB
testcase_13 AC 430 ms
117,712 KB
testcase_14 AC 794 ms
165,640 KB
testcase_15 AC 738 ms
154,860 KB
testcase_16 AC 432 ms
115,672 KB
testcase_17 AC 590 ms
133,356 KB
testcase_18 AC 482 ms
126,732 KB
testcase_19 AC 570 ms
132,556 KB
testcase_20 AC 775 ms
165,892 KB
testcase_21 AC 126 ms
84,000 KB
testcase_22 AC 578 ms
134,312 KB
testcase_23 AC 616 ms
140,848 KB
testcase_24 AC 439 ms
121,256 KB
testcase_25 AC 798 ms
165,784 KB
testcase_26 AC 652 ms
145,840 KB
testcase_27 AC 749 ms
157,676 KB
testcase_28 AC 732 ms
153,256 KB
testcase_29 AC 719 ms
154,940 KB
testcase_30 AC 442 ms
115,248 KB
testcase_31 AC 386 ms
113,668 KB
testcase_32 AC 373 ms
110,704 KB
testcase_33 AC 411 ms
112,400 KB
testcase_34 AC 706 ms
148,708 KB
testcase_35 AC 156 ms
84,896 KB
testcase_36 AC 687 ms
149,444 KB
testcase_37 AC 625 ms
138,696 KB
testcase_38 AC 262 ms
93,532 KB
testcase_39 AC 408 ms
113,404 KB
testcase_40 AC 296 ms
108,044 KB
testcase_41 AC 548 ms
127,728 KB
testcase_42 AC 38 ms
53,732 KB
testcase_43 AC 38 ms
53,068 KB
testcase_44 AC 40 ms
53,872 KB
testcase_45 AC 731 ms
168,436 KB
testcase_46 AC 731 ms
168,044 KB
testcase_47 AC 731 ms
168,228 KB
testcase_48 AC 730 ms
168,128 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


# inputna
n,m,X = list(map(int, input().split()))
M = 10**9+7
xyz = [list(map(int, input().split())) for _ in range(m)]
for i in range(m):
    xyz[i] = (xyz[i][0]-1, xyz[i][1]-1, xyz[i][2])
xyz.sort(key=lambda x: x[2])

class UnionFindTree:
    def __init__(self, n):
        self.n = n
        self.parent = list(range(n))
        self.size = [1] * n

    def root(self, i):
        inter = set()
        while self.parent[i]!=i:
            inter.add(i)
            i = self.parent[i]
        r = i
        for i in inter:
            self.parent[i] = r
        return r

    def connect(self, i, j):
        ri = self.root(i)
        rj = self.root(j)
        if ri==rj:
            return
        if self.size[ri]<self.size[rj]:
            self.parent[ri] = rj
            self.size[rj] += self.size[ri]
        else:
            self.parent[rj] = ri
            self.size[ri] += self.size[rj]
ans = 0
uf = UnionFindTree(n)
ss = [0] * n
es = [[] for _ in range(n)]
for x,y,z in xyz:
    rx = uf.root(x)
    ry = uf.root(y)
    if rx==ry:
        continue
    uf.connect(x,y)
    es[x].append((y,z))
    es[y].append((x,z))
ans = 0
size = [None]*n
start = 0
def sub(u, p):
    global ans
    res = 0
    for v,z in es[u]:
        if v==p:
            continue
        size = sub(v,u)
        res += size
        ans = ans + size * (n-size) * pow(X,z,M)
        ans %= M
    return res+1
sub(0,-1)
print(ans%M)
0