結果
問題 | No.1207 グラフX |
ユーザー | e869120 |
提出日時 | 2021-02-26 08:32:25 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 544 ms / 2,000 ms |
コード長 | 1,659 bytes |
コンパイル時間 | 788 ms |
コンパイル使用メモリ | 76,984 KB |
実行使用メモリ | 32,844 KB |
最終ジャッジ日時 | 2024-04-09 22:02:37 |
合計ジャッジ時間 | 21,267 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 495 ms
24,192 KB |
testcase_01 | AC | 512 ms
24,172 KB |
testcase_02 | AC | 510 ms
24,088 KB |
testcase_03 | AC | 519 ms
24,380 KB |
testcase_04 | AC | 515 ms
24,324 KB |
testcase_05 | AC | 544 ms
32,664 KB |
testcase_06 | AC | 537 ms
32,344 KB |
testcase_07 | AC | 538 ms
32,664 KB |
testcase_08 | AC | 376 ms
20,688 KB |
testcase_09 | AC | 422 ms
21,592 KB |
testcase_10 | AC | 519 ms
28,488 KB |
testcase_11 | AC | 522 ms
32,844 KB |
testcase_12 | AC | 386 ms
21,068 KB |
testcase_13 | AC | 201 ms
16,616 KB |
testcase_14 | AC | 501 ms
23,896 KB |
testcase_15 | AC | 408 ms
21,836 KB |
testcase_16 | AC | 194 ms
17,572 KB |
testcase_17 | AC | 315 ms
19,632 KB |
testcase_18 | AC | 285 ms
20,428 KB |
testcase_19 | AC | 291 ms
18,324 KB |
testcase_20 | AC | 509 ms
23,892 KB |
testcase_21 | AC | 33 ms
14,716 KB |
testcase_22 | AC | 319 ms
20,172 KB |
testcase_23 | AC | 357 ms
20,376 KB |
testcase_24 | AC | 255 ms
18,684 KB |
testcase_25 | AC | 498 ms
23,824 KB |
testcase_26 | AC | 382 ms
21,576 KB |
testcase_27 | AC | 451 ms
23,160 KB |
testcase_28 | AC | 419 ms
21,680 KB |
testcase_29 | AC | 451 ms
22,364 KB |
testcase_30 | AC | 212 ms
17,268 KB |
testcase_31 | AC | 161 ms
16,972 KB |
testcase_32 | AC | 192 ms
17,288 KB |
testcase_33 | AC | 198 ms
17,436 KB |
testcase_34 | AC | 400 ms
21,236 KB |
testcase_35 | AC | 35 ms
14,220 KB |
testcase_36 | AC | 400 ms
21,460 KB |
testcase_37 | AC | 341 ms
20,552 KB |
testcase_38 | AC | 94 ms
15,976 KB |
testcase_39 | AC | 207 ms
18,896 KB |
testcase_40 | AC | 120 ms
15,316 KB |
testcase_41 | AC | 274 ms
18,804 KB |
testcase_42 | AC | 4 ms
14,280 KB |
testcase_43 | AC | 4 ms
15,948 KB |
testcase_44 | AC | 4 ms
15,816 KB |
testcase_45 | AC | 472 ms
23,932 KB |
testcase_46 | AC | 487 ms
23,804 KB |
testcase_47 | AC | 486 ms
24,060 KB |
testcase_48 | AC | 482 ms
24,060 KB |
ソースコード
#include <iostream> #include <vector> #include <algorithm> using namespace std; long long mod = 1000000007; class UnionFind { public: vector<int> par; void init(int sz) { par.resize(sz, -1); } int root(int pos) { if (par[pos] == -1) return pos; par[pos] = root(par[pos]); return par[pos]; } void unite(int u, int v) { u = root(u); v = root(v); if (u != v) par[u] = v; } bool same(int u, int v) { u = root(u); v = root(v); if (u == v) return true; return false; } }; long long modpow(long long a, long long b, long long m) { long long p = 1, q = a; for (int i = 0; i < 62; i++) { if ((b / (1LL << i)) % 2LL == 1) { p *= q; p %= m; } q *= q; q %= m; } return p; } // 入力 long long N, M, X; long long A[1 << 18], B[1 << 18], C[1 << 18]; // 木の情報 UnionFind UF; vector<int> G[1 << 18]; int dp[1 << 18]; bool used[1 << 18]; void dfs(int pos) { dp[pos] = 1; for (int i : G[pos]) { if (dp[i] >= 1) continue; dfs(i); dp[pos] += dp[i]; } } int main() { // Step #1. 入力 cin >> N >> M >> X; for (int i = 1; i <= M; i++) cin >> A[i] >> B[i] >> C[i]; // Step #2. UF UF.init(N + 2); for (int i = 1; i <= M; i++) { if (UF.same(A[i], B[i]) == false) { UF.unite(A[i], B[i]); G[A[i]].push_back(B[i]); G[B[i]].push_back(A[i]); used[i] = true; } } // Step #3. 答えを求める long long Answer = 0; dfs(1); for (int i = 1; i <= M; i++) { if (used[i] == false) continue; long long cost = modpow(X, C[i], mod); long long t1 = min(dp[A[i]], dp[B[i]]); long long t2 = N - t1; Answer += (t1 * t2 % mod) * cost % mod; Answer %= mod; } cout << Answer << endl; return 0; }