結果
問題 | No.1207 グラフX |
ユーザー | mlihua09 |
提出日時 | 2020-08-30 14:32:57 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 995 ms / 2,000 ms |
コード長 | 1,655 bytes |
コンパイル時間 | 703 ms |
コンパイル使用メモリ | 82,360 KB |
実行使用メモリ | 172,988 KB |
最終ジャッジ日時 | 2024-04-27 07:34:29 |
合計ジャッジ時間 | 32,634 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 737 ms
165,188 KB |
testcase_01 | AC | 745 ms
165,056 KB |
testcase_02 | AC | 912 ms
165,004 KB |
testcase_03 | AC | 758 ms
164,556 KB |
testcase_04 | AC | 738 ms
165,916 KB |
testcase_05 | AC | 991 ms
167,500 KB |
testcase_06 | AC | 969 ms
170,092 KB |
testcase_07 | AC | 977 ms
170,552 KB |
testcase_08 | AC | 690 ms
140,392 KB |
testcase_09 | AC | 693 ms
150,940 KB |
testcase_10 | AC | 995 ms
167,868 KB |
testcase_11 | AC | 980 ms
170,712 KB |
testcase_12 | AC | 652 ms
140,672 KB |
testcase_13 | AC | 417 ms
104,824 KB |
testcase_14 | AC | 763 ms
164,164 KB |
testcase_15 | AC | 687 ms
146,548 KB |
testcase_16 | AC | 432 ms
107,312 KB |
testcase_17 | AC | 573 ms
131,940 KB |
testcase_18 | AC | 477 ms
127,192 KB |
testcase_19 | AC | 551 ms
121,928 KB |
testcase_20 | AC | 768 ms
165,500 KB |
testcase_21 | AC | 152 ms
81,504 KB |
testcase_22 | AC | 685 ms
130,656 KB |
testcase_23 | AC | 593 ms
140,140 KB |
testcase_24 | AC | 442 ms
122,864 KB |
testcase_25 | AC | 776 ms
166,176 KB |
testcase_26 | AC | 639 ms
144,204 KB |
testcase_27 | AC | 733 ms
154,112 KB |
testcase_28 | AC | 703 ms
148,524 KB |
testcase_29 | AC | 693 ms
155,632 KB |
testcase_30 | AC | 434 ms
110,580 KB |
testcase_31 | AC | 380 ms
99,324 KB |
testcase_32 | AC | 391 ms
110,248 KB |
testcase_33 | AC | 402 ms
110,472 KB |
testcase_34 | AC | 685 ms
147,420 KB |
testcase_35 | AC | 176 ms
82,060 KB |
testcase_36 | AC | 654 ms
147,740 KB |
testcase_37 | AC | 618 ms
138,880 KB |
testcase_38 | AC | 260 ms
89,272 KB |
testcase_39 | AC | 408 ms
113,608 KB |
testcase_40 | AC | 304 ms
94,668 KB |
testcase_41 | AC | 605 ms
118,580 KB |
testcase_42 | AC | 47 ms
52,536 KB |
testcase_43 | AC | 46 ms
52,596 KB |
testcase_44 | AC | 49 ms
53,224 KB |
testcase_45 | AC | 679 ms
172,988 KB |
testcase_46 | AC | 689 ms
172,788 KB |
testcase_47 | AC | 689 ms
172,916 KB |
testcase_48 | AC | 676 ms
172,920 KB |
ソースコード
N, M, X = map(int, input().split()) XYZ = [] p = 10 ** 9 + 7 class UnionFind: def __init__(self, N): self.N = N self.P = [-1] * N def Find(self, x): if self.P[x] < 0: return x else: self.P[x] = self.Find(self.P[x]) return self.P[x] def query(self, x, y): x -= 1 y -= 1 x = self.Find(x) y = self.Find(y) if x == y: return False if self.P[x] > self.P[y]: x, y = y, x self.P[x], self.P[y] = self.P[x] + self.P[y], x return True G = UnionFind(N) for i in range(M): x, y, z = map(int, input().split()) XYZ += [[z, x, y]] XYZ.sort() E = [] V1 = [[] for i in range(N)] for z, x, y in XYZ: if G.query(x, y): E += [[x - 1, y - 1, z]] V1[x - 1] += [y - 1] V1[y - 1] += [x - 1] que = [0] P = [-1] * N P[0] = 0 V = [[] for i in range(N)] while que: q = que.pop() for v in V1[q]: if P[v] == -1: V[q] += [v] P[v] = q que += V[q] A = [1] * N que = [0] while que: q = que.pop() if V[q]: que += [V[q].pop()] else: if q == 0: break A[P[q]] += A[q] que += [P[q]] ans = 0 for x, y, z in E: if P[x] != y: x, y = y, x ans += A[x] * (N - A[x]) % p * pow(X, z, p) % p ans %= p print(ans)