結果
問題 | No.1207 グラフX |
ユーザー | hir0 |
提出日時 | 2020-09-08 15:12:32 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 192 ms / 2,000 ms |
コード長 | 5,008 bytes |
コンパイル時間 | 2,607 ms |
コンパイル使用メモリ | 181,288 KB |
実行使用メモリ | 37,124 KB |
最終ジャッジ日時 | 2023-08-19 21:58:36 |
合計ジャッジ時間 | 13,461 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 136 ms
20,340 KB |
testcase_01 | AC | 137 ms
20,276 KB |
testcase_02 | AC | 136 ms
20,292 KB |
testcase_03 | AC | 136 ms
20,360 KB |
testcase_04 | AC | 138 ms
20,276 KB |
testcase_05 | AC | 182 ms
36,984 KB |
testcase_06 | AC | 192 ms
37,048 KB |
testcase_07 | AC | 185 ms
37,124 KB |
testcase_08 | AC | 110 ms
13,532 KB |
testcase_09 | AC | 116 ms
17,344 KB |
testcase_10 | AC | 181 ms
29,876 KB |
testcase_11 | AC | 182 ms
37,112 KB |
testcase_12 | AC | 108 ms
14,428 KB |
testcase_13 | AC | 63 ms
5,896 KB |
testcase_14 | AC | 131 ms
19,444 KB |
testcase_15 | AC | 116 ms
15,676 KB |
testcase_16 | AC | 61 ms
7,128 KB |
testcase_17 | AC | 92 ms
12,536 KB |
testcase_18 | AC | 73 ms
12,788 KB |
testcase_19 | AC | 89 ms
9,228 KB |
testcase_20 | AC | 139 ms
20,000 KB |
testcase_21 | AC | 11 ms
4,376 KB |
testcase_22 | AC | 88 ms
12,772 KB |
testcase_23 | AC | 98 ms
14,248 KB |
testcase_24 | AC | 65 ms
11,896 KB |
testcase_25 | AC | 135 ms
19,844 KB |
testcase_26 | AC | 107 ms
15,492 KB |
testcase_27 | AC | 125 ms
17,972 KB |
testcase_28 | AC | 121 ms
17,048 KB |
testcase_29 | AC | 118 ms
17,628 KB |
testcase_30 | AC | 62 ms
8,924 KB |
testcase_31 | AC | 53 ms
4,932 KB |
testcase_32 | AC | 52 ms
9,420 KB |
testcase_33 | AC | 55 ms
9,092 KB |
testcase_34 | AC | 114 ms
15,608 KB |
testcase_35 | AC | 13 ms
4,384 KB |
testcase_36 | AC | 119 ms
16,848 KB |
testcase_37 | AC | 99 ms
13,284 KB |
testcase_38 | AC | 27 ms
5,612 KB |
testcase_39 | AC | 58 ms
10,308 KB |
testcase_40 | AC | 41 ms
4,376 KB |
testcase_41 | AC | 81 ms
9,880 KB |
testcase_42 | AC | 1 ms
4,380 KB |
testcase_43 | AC | 2 ms
4,376 KB |
testcase_44 | AC | 1 ms
4,380 KB |
testcase_45 | AC | 130 ms
20,448 KB |
testcase_46 | AC | 126 ms
20,852 KB |
testcase_47 | AC | 130 ms
20,408 KB |
testcase_48 | AC | 125 ms
20,252 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define pa pair<int, int> #define pal pair<long long, long long> #define pali pair<long long, int> #define pad pair<double, double> #define pb push_back #define mp make_pair #define COUT(v) \ for (int64_t i = 0; i < (v).size(); ++i) \ { \ cout << v.at(i) << endl; \ } #define REP(i, n) for (int64_t i = 0; i < n; ++i) #define FOR(i, r, n) for (int64_t i = (r); i < n; ++i) #define VIN(v) \ for (int64_t i = 0; i < (v).size(); ++i) \ { \ cin >> (v).at(i); \ } typedef vector<bool> bvec; typedef vector<int> ivec; typedef vector<long long> lvec; typedef vector<double> dvec; typedef vector<pa> pavec; typedef vector<pali> palivec; typedef vector<pal> palvec; typedef vector<vector<bool>> bmat; typedef vector<vector<int>> imat; typedef vector<vector<long long>> lmat; typedef vector<string> svec; typedef vector<vector<string>> smat; const ll infll = (1LL << 60) - 1; const int inf = (1 << 30) - 1; const ll MOD = 1000000007; ll gcd(ll x, ll y) { ll r = x % y; if (r == 0) return y; else return gcd(y, r); } ll lcm(ll x, ll y) { return x * y / gcd(x, y); } lvec mfactor(ll n) { bvec ip(n, true); lvec mf(n, -1); ip[0] = false; ip[1] = false; mf[0] = 0; mf[1] = 1; REP(i, n) { if (ip[i]) { mf[i] = i; for (ll j = i * i; j < n; j += i) { ip[j] = false; if (mf[j] == -1) mf[j] = i; } } } return mf; } palivec get_prime(ll n, const lvec &mf) { palivec plist; while (n != 1) { int cnt = 0; ll m = mf[n]; while (mf[n] == m) { cnt++; n /= m; } plist.pb(pali(m, cnt)); } return plist; } void COMinit(int m, lvec &fac, lvec &finv) { lvec inv(m); fac[0] = fac[1] = 1; finv[0] = finv[1] = 1; inv[1] = 1; for (int i = 2; i < m; i++) { fac[i] = fac[i - 1] * i % MOD; inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD; finv[i] = finv[i - 1] * inv[i] % MOD; } } ll pow_mod(ll a, ll n) { ll x = 1; a %= MOD; while (n > 0) { if (n & 1) { x = x * a % MOD; } a = a * a % MOD; n >>= 1; } return x; } ll pow_mod2(ll a, ll n) { ll x = 1; while (n > 0) { if (n & 1) { x = x * a; } a = a * a; n >>= 1; } return x; } ll COM(int n, int k, const lvec &fac, const lvec &finv) { if (n < k) return 0; if (n < 0 || k < 0) return 0; return (fac[n] * (finv[k] * finv[n - k] % MOD)) % MOD; } ll modinv(ll a, ll m) { ll b = m, u = 1, v = 0; while (b) { ll t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } u %= m; if (u < 0) u += m; return u; } // union by size + path having class UnionFind { public: vector<ll> par; vector<ll> siz; // Constructor UnionFind(ll sz_) : par(sz_), siz(sz_, 1LL) { for (ll i = 0; i < sz_; ++i) par[i] = i; } void init(ll sz_) { par.resize(sz_); siz.assign(sz_, 1LL); for (ll i = 0; i < sz_; ++i) par[i] = i; } // Member Function // Find ll root(ll x) { while (par[x] != x) { x = par[x] = par[par[x]]; } return x; } // Union(Unite, Merge) bool merge(ll x, ll y) { x = root(x); y = root(y); if (x == y) return false; if (siz[x] < siz[y]) swap(x, y); siz[x] += siz[y]; par[y] = x; return true; } bool issame(ll x, ll y) { return root(x) == root(y); } ll size(ll x) { return siz[root(x)]; } }; int main() { cin.tie(0); ios::sync_with_stdio(false); ll n, m, x; cin >> n >> m >> x; vector<vector<pal>> g(n); UnionFind u(n); for (int i = 0; i < m; i++) { ll a, b, z; cin >> a >> b >> z; --a, --b; if (!u.issame(a, b)) { u.merge(a, b); g[a].pb(pal(b, z)); g[b].pb(pal(a, z)); } } ll ans = 0; bvec flg(n, false); function<ll(ll, ll)> dfs = [&](ll k, ll zz) { ll siz = 1; flg[k] = true; for (auto v : g[k]) { if (!flg[v.first]) { siz += dfs(v.first, v.second); } } ans += pow_mod(x, zz) * ((siz * (n - siz)) % MOD); ans %= MOD; return siz; }; dfs(0, 0); cout << ans << endl; }