結果
問題 | No.1207 グラフX |
ユーザー | Series_205 |
提出日時 | 2020-08-30 13:34:37 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 217 ms / 2,000 ms |
コード長 | 3,812 bytes |
コンパイル時間 | 3,424 ms |
コンパイル使用メモリ | 204,444 KB |
実行使用メモリ | 31,276 KB |
最終ジャッジ日時 | 2023-08-09 11:52:45 |
合計ジャッジ時間 | 13,125 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 159 ms
17,220 KB |
testcase_01 | AC | 155 ms
17,164 KB |
testcase_02 | AC | 151 ms
17,268 KB |
testcase_03 | AC | 155 ms
17,456 KB |
testcase_04 | AC | 154 ms
17,160 KB |
testcase_05 | AC | 217 ms
31,276 KB |
testcase_06 | AC | 212 ms
31,240 KB |
testcase_07 | AC | 215 ms
31,212 KB |
testcase_08 | AC | 127 ms
13,244 KB |
testcase_09 | AC | 136 ms
14,692 KB |
testcase_10 | AC | 208 ms
24,048 KB |
testcase_11 | AC | 215 ms
31,204 KB |
testcase_12 | AC | 126 ms
13,596 KB |
testcase_13 | AC | 64 ms
9,568 KB |
testcase_14 | AC | 153 ms
16,556 KB |
testcase_15 | AC | 136 ms
14,520 KB |
testcase_16 | AC | 65 ms
9,820 KB |
testcase_17 | AC | 100 ms
12,648 KB |
testcase_18 | AC | 82 ms
13,056 KB |
testcase_19 | AC | 96 ms
10,876 KB |
testcase_20 | AC | 154 ms
16,916 KB |
testcase_21 | AC | 14 ms
8,144 KB |
testcase_22 | AC | 101 ms
12,820 KB |
testcase_23 | AC | 111 ms
13,764 KB |
testcase_24 | AC | 73 ms
12,444 KB |
testcase_25 | AC | 159 ms
16,744 KB |
testcase_26 | AC | 118 ms
14,332 KB |
testcase_27 | AC | 141 ms
15,592 KB |
testcase_28 | AC | 136 ms
14,768 KB |
testcase_29 | AC | 135 ms
15,700 KB |
testcase_30 | AC | 68 ms
10,688 KB |
testcase_31 | AC | 56 ms
9,116 KB |
testcase_32 | AC | 58 ms
10,944 KB |
testcase_33 | AC | 61 ms
10,880 KB |
testcase_34 | AC | 124 ms
14,452 KB |
testcase_35 | AC | 14 ms
8,236 KB |
testcase_36 | AC | 124 ms
14,796 KB |
testcase_37 | AC | 108 ms
13,352 KB |
testcase_38 | AC | 30 ms
9,360 KB |
testcase_39 | AC | 65 ms
11,340 KB |
testcase_40 | AC | 43 ms
8,336 KB |
testcase_41 | AC | 89 ms
11,056 KB |
testcase_42 | AC | 5 ms
8,084 KB |
testcase_43 | AC | 5 ms
8,072 KB |
testcase_44 | AC | 5 ms
8,148 KB |
testcase_45 | AC | 150 ms
17,264 KB |
testcase_46 | AC | 147 ms
17,260 KB |
testcase_47 | AC | 151 ms
17,180 KB |
testcase_48 | AC | 147 ms
17,276 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; }