結果
問題 | No.1207 グラフX |
ユーザー | marroncastle |
提出日時 | 2020-08-30 17:25:05 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,932 ms / 2,000 ms |
コード長 | 1,788 bytes |
コンパイル時間 | 390 ms |
コンパイル使用メモリ | 82,072 KB |
実行使用メモリ | 392,644 KB |
最終ジャッジ日時 | 2024-12-15 02:42:52 |
合計ジャッジ時間 | 35,789 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 610 ms
136,824 KB |
testcase_01 | AC | 613 ms
136,760 KB |
testcase_02 | AC | 621 ms
136,148 KB |
testcase_03 | AC | 604 ms
136,360 KB |
testcase_04 | AC | 606 ms
137,148 KB |
testcase_05 | AC | 1,404 ms
315,432 KB |
testcase_06 | AC | 1,414 ms
314,356 KB |
testcase_07 | AC | 1,373 ms
316,680 KB |
testcase_08 | AC | 601 ms
118,816 KB |
testcase_09 | AC | 606 ms
121,932 KB |
testcase_10 | AC | 1,932 ms
392,644 KB |
testcase_11 | AC | 1,439 ms
321,448 KB |
testcase_12 | AC | 580 ms
118,436 KB |
testcase_13 | AC | 420 ms
99,312 KB |
testcase_14 | AC | 627 ms
135,124 KB |
testcase_15 | AC | 598 ms
123,736 KB |
testcase_16 | AC | 403 ms
99,336 KB |
testcase_17 | AC | 491 ms
111,764 KB |
testcase_18 | AC | 404 ms
111,132 KB |
testcase_19 | AC | 513 ms
108,420 KB |
testcase_20 | AC | 630 ms
135,264 KB |
testcase_21 | AC | 135 ms
80,820 KB |
testcase_22 | AC | 489 ms
110,288 KB |
testcase_23 | AC | 500 ms
115,144 KB |
testcase_24 | AC | 361 ms
106,416 KB |
testcase_25 | AC | 644 ms
134,592 KB |
testcase_26 | AC | 532 ms
122,108 KB |
testcase_27 | AC | 597 ms
127,128 KB |
testcase_28 | AC | 600 ms
124,688 KB |
testcase_29 | AC | 571 ms
127,560 KB |
testcase_30 | AC | 393 ms
99,776 KB |
testcase_31 | AC | 384 ms
96,760 KB |
testcase_32 | AC | 324 ms
98,728 KB |
testcase_33 | AC | 359 ms
99,932 KB |
testcase_34 | AC | 580 ms
119,876 KB |
testcase_35 | AC | 173 ms
81,620 KB |
testcase_36 | AC | 566 ms
123,336 KB |
testcase_37 | AC | 522 ms
114,056 KB |
testcase_38 | AC | 249 ms
86,616 KB |
testcase_39 | AC | 360 ms
100,868 KB |
testcase_40 | AC | 288 ms
92,760 KB |
testcase_41 | AC | 471 ms
105,960 KB |
testcase_42 | AC | 39 ms
53,356 KB |
testcase_43 | AC | 39 ms
53,012 KB |
testcase_44 | AC | 39 ms
54,340 KB |
testcase_45 | AC | 600 ms
132,908 KB |
testcase_46 | AC | 601 ms
132,980 KB |
testcase_47 | AC | 589 ms
133,332 KB |
testcase_48 | AC | 603 ms
132,928 KB |
ソースコード
class UnionFind():def __init__(self, n):self.n = nself.parents = [-1] * ndef find(self, x):if self.parents[x] < 0:return xelse:self.parents[x] = self.find(self.parents[x])return self.parents[x]def union(self, x, y):x = self.find(x)y = self.find(y)if x == y:returnif self.parents[x] > self.parents[y]:x, y = y, xself.parents[x] += self.parents[y]self.parents[y] = xdef same(self, x, y):return self.find(x) == self.find(y)def roots(self):return [i for i, x in enumerate(self.parents) if x < 0]def num_roots(self):return len([i for i, x in enumerate(self.parents) if x < 0])def members(self, x):root = self.find(x)return [i for i in range(self.n) if self.find(i) == root]def num_members(self,x):return abs(self.parents[self.find(x)])def __str__(self):return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())import syssys.setrecursionlimit(10**6)def dfs(v):ans = 0for unum in edge[v]:u,num = divmod(unum,mod2)if used[num]==False:used[num] = Truev_num = dfs(u)e_cnt[num] = v_num*(N-v_num)ans += v_numreturn ans+1N, M, X = map(int, input().split())A = [list(map(int, input().split())) for _ in range(M)]uf = UnionFind(N)edge = [[] for _ in range(N)]e_length = [0]*(N-1)num = 0mod2 = 10**6for x,y,z in A:x -= 1y -= 1if not uf.same(x,y):uf.union(x,y)e_length[num] = zedge[x].append(y*mod2+num)edge[y].append(x*mod2+num)num += 1if num==N-1:breakdel ufe_cnt = [0]*(N-1)used = [False]*(N-1)dfs(0)mod = 10**9+7ans = 0for i in range(N-1):ans += e_cnt[i]*pow(X,e_length[i],mod)ans %= modprint(ans)