結果
問題 | No.1207 グラフX |
ユーザー | Series_205 |
提出日時 | 2020-08-30 13:34:37 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 157 ms / 2,000 ms |
コード長 | 3,812 bytes |
コンパイル時間 | 1,811 ms |
コンパイル使用メモリ | 208,288 KB |
実行使用メモリ | 31,372 KB |
最終ジャッジ日時 | 2024-04-27 06:58:53 |
合計ジャッジ時間 | 8,538 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 122 ms
17,364 KB |
testcase_01 | AC | 123 ms
17,372 KB |
testcase_02 | AC | 157 ms
17,260 KB |
testcase_03 | AC | 114 ms
17,248 KB |
testcase_04 | AC | 113 ms
17,284 KB |
testcase_05 | AC | 145 ms
31,300 KB |
testcase_06 | AC | 152 ms
31,256 KB |
testcase_07 | AC | 147 ms
31,300 KB |
testcase_08 | AC | 90 ms
13,312 KB |
testcase_09 | AC | 99 ms
15,132 KB |
testcase_10 | AC | 143 ms
24,124 KB |
testcase_11 | AC | 155 ms
31,372 KB |
testcase_12 | AC | 88 ms
13,976 KB |
testcase_13 | AC | 58 ms
9,576 KB |
testcase_14 | AC | 108 ms
16,836 KB |
testcase_15 | AC | 102 ms
14,612 KB |
testcase_16 | AC | 55 ms
9,908 KB |
testcase_17 | AC | 78 ms
13,012 KB |
testcase_18 | AC | 62 ms
13,240 KB |
testcase_19 | AC | 79 ms
11,156 KB |
testcase_20 | AC | 117 ms
17,132 KB |
testcase_21 | AC | 12 ms
8,252 KB |
testcase_22 | AC | 75 ms
13,052 KB |
testcase_23 | AC | 83 ms
14,016 KB |
testcase_24 | AC | 59 ms
12,660 KB |
testcase_25 | AC | 113 ms
17,004 KB |
testcase_26 | AC | 93 ms
14,556 KB |
testcase_27 | AC | 108 ms
15,956 KB |
testcase_28 | AC | 107 ms
15,068 KB |
testcase_29 | AC | 105 ms
15,848 KB |
testcase_30 | AC | 55 ms
10,916 KB |
testcase_31 | AC | 49 ms
9,668 KB |
testcase_32 | AC | 47 ms
11,248 KB |
testcase_33 | AC | 51 ms
11,136 KB |
testcase_34 | AC | 99 ms
14,660 KB |
testcase_35 | AC | 13 ms
8,516 KB |
testcase_36 | AC | 96 ms
14,940 KB |
testcase_37 | AC | 87 ms
13,356 KB |
testcase_38 | AC | 26 ms
9,536 KB |
testcase_39 | AC | 52 ms
11,488 KB |
testcase_40 | AC | 39 ms
8,252 KB |
testcase_41 | AC | 72 ms
11,248 KB |
testcase_42 | AC | 4 ms
8,032 KB |
testcase_43 | AC | 4 ms
8,516 KB |
testcase_44 | AC | 4 ms
8,224 KB |
testcase_45 | AC | 115 ms
17,292 KB |
testcase_46 | AC | 111 ms
17,352 KB |
testcase_47 | AC | 105 ms
17,356 KB |
testcase_48 | AC | 117 ms
17,356 KB |
ソースコード
#include <bits/stdc++.h> #define FOR(i, a, n) for(ll i = (ll)a; i < (ll)n; i++) #define FORR(i, n) for(ll i = (ll)n - 1LL; i >= 0LL; i--) #define rep(i, n) FOR(i, 0, n) #define ALL(x) begin(x), end(x) using namespace std; using ll = long long; constexpr ll Mod = 998244353; constexpr ll mod = 1e9 + 7; constexpr ll inf = 1LL << 60; const double PI = acos(-1); template <typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); } template <typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); } /*-------------------------------------------*/ template <int M> class ModInt { int x; public: constexpr ModInt() : x(0) {} constexpr ModInt(int64_t y) : x(y >= 0 ? y % M : (M - (-y) % M) % M) {} constexpr ModInt &operator+=(const ModInt p) { if((x += p.x) >= M) x -= M; return *this; } constexpr ModInt &operator-=(const ModInt p) { if((x += M - p.x) >= M) x -= M; return *this; } constexpr ModInt &operator*=(const ModInt p) { x = (int)(1LL * x * p.x % M); return *this; } constexpr ModInt &operator/=(const ModInt p) { *this *= p.inverse(); return *this; } constexpr ModInt operator-() const { return ModInt(-x); } constexpr ModInt operator+(const ModInt p) const { return ModInt(*this) += p; } constexpr ModInt operator-(const ModInt p) const { return ModInt(*this) -= p; } constexpr ModInt operator*(const ModInt p) const { return ModInt(*this) *= p; } constexpr ModInt operator/(const ModInt p) const { return ModInt(*this) /= p; } constexpr bool operator==(const ModInt p) const { return x == p.x; } constexpr bool operator!=(const ModInt p) const { return x != p.x; } constexpr ModInt inverse() const { int a = x, b = M, u = 1, v = 0, t = 0; while(b > 0) { t = a / b; swap(a -= t * b, b); swap(u -= t * v, v); } return ModInt(u); } constexpr ModInt pow(int64_t k) const { ModInt ret(1), mul(x); while(k > 0) { if(k & 1) ret *= mul; mul *= mul; k >>= 1; } return ret; } constexpr friend ostream &operator<<(ostream &os, const ModInt &p) { return os << p.x; } constexpr friend istream &operator>>(istream &is, ModInt &a) { int64_t t = 0; is >> t; a = ModInt(t); return (is); } }; using mint = ModInt<mod>; class UnionFind { vector<int> par; int c; public: UnionFind(int n) : par(n, -1), c(n) {} int find(int x) { return par[x] < 0 ? x : par[x] = find(par[x]); } int size(int x) { return -par[find(x)]; } int count() const { return c; } bool same(int x, int y) { return find(x) == find(y); } bool unite(int x, int y) { if((x = find(x)) == (y = find(y))) return false; if(par[x] < par[y]) swap(x, y); par[y] += par[x]; par[x] = y; return c--; } }; int n, m; mint x, ans; vector<pair<int, mint>> g[200009]; int sz[200009]; void dfs(int v, int p) { sz[v] = 1; for(auto [u, cost] : g[v]) { if(p != u) { dfs(u, v); ans += cost * sz[u] * (n - sz[u]); sz[v] += sz[u]; } } } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); cin >> n >> m >> x; UnionFind uf(n); rep(i, m) { int a, b, z; cin >> a >> b >> z; a--; b--; if(uf.unite(a, b)) { mint cost = x.pow(z); g[a].emplace_back(b, cost); g[b].emplace_back(a, cost); } } dfs(0, -1); cout << ans << endl; return 0; }