結果
問題 | No.1207 グラフX |
ユーザー | milanis48663220 |
提出日時 | 2020-08-31 01:54:33 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 177 ms / 2,000 ms |
コード長 | 3,323 bytes |
コンパイル時間 | 819 ms |
コンパイル使用メモリ | 88,624 KB |
実行使用メモリ | 31,104 KB |
最終ジャッジ日時 | 2024-04-27 13:54:08 |
合計ジャッジ時間 | 8,859 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 148 ms
19,304 KB |
testcase_01 | AC | 148 ms
19,304 KB |
testcase_02 | AC | 150 ms
19,336 KB |
testcase_03 | AC | 141 ms
19,436 KB |
testcase_04 | AC | 147 ms
19,304 KB |
testcase_05 | AC | 177 ms
30,976 KB |
testcase_06 | AC | 174 ms
30,976 KB |
testcase_07 | AC | 176 ms
31,104 KB |
testcase_08 | AC | 119 ms
15,488 KB |
testcase_09 | AC | 120 ms
16,996 KB |
testcase_10 | AC | 170 ms
25,344 KB |
testcase_11 | AC | 174 ms
30,976 KB |
testcase_12 | AC | 114 ms
15,872 KB |
testcase_13 | AC | 63 ms
11,392 KB |
testcase_14 | AC | 142 ms
18,852 KB |
testcase_15 | AC | 125 ms
16,768 KB |
testcase_16 | AC | 63 ms
11,776 KB |
testcase_17 | AC | 94 ms
14,464 KB |
testcase_18 | AC | 80 ms
14,336 KB |
testcase_19 | AC | 92 ms
13,440 KB |
testcase_20 | AC | 144 ms
19,216 KB |
testcase_21 | AC | 13 ms
8,832 KB |
testcase_22 | AC | 91 ms
14,720 KB |
testcase_23 | AC | 99 ms
15,616 KB |
testcase_24 | AC | 73 ms
13,696 KB |
testcase_25 | AC | 142 ms
18,972 KB |
testcase_26 | AC | 105 ms
16,256 KB |
testcase_27 | AC | 131 ms
18,020 KB |
testcase_28 | AC | 120 ms
17,164 KB |
testcase_29 | AC | 118 ms
17,608 KB |
testcase_30 | AC | 63 ms
12,416 KB |
testcase_31 | AC | 55 ms
10,880 KB |
testcase_32 | AC | 55 ms
12,160 KB |
testcase_33 | AC | 58 ms
12,160 KB |
testcase_34 | AC | 119 ms
16,508 KB |
testcase_35 | AC | 14 ms
8,832 KB |
testcase_36 | AC | 112 ms
16,772 KB |
testcase_37 | AC | 107 ms
15,232 KB |
testcase_38 | AC | 30 ms
10,240 KB |
testcase_39 | AC | 60 ms
12,540 KB |
testcase_40 | AC | 42 ms
9,984 KB |
testcase_41 | AC | 86 ms
13,184 KB |
testcase_42 | AC | 5 ms
8,192 KB |
testcase_43 | AC | 4 ms
8,064 KB |
testcase_44 | AC | 4 ms
8,192 KB |
testcase_45 | AC | 132 ms
19,288 KB |
testcase_46 | AC | 138 ms
19,292 KB |
testcase_47 | AC | 137 ms
19,288 KB |
testcase_48 | AC | 137 ms
19,288 KB |
ソースコード
#include <iostream> #include <algorithm> #include <iomanip> #include <vector> #include <queue> #include <set> #include <map> using namespace std; typedef long long ll; struct UnionFind { vector<int> data; UnionFind(int size) : data(size, -1) { } bool unionSet(int x, int y) { x = root(x); y = root(y); if (x != y) { if (data[y] < data[x]) swap(x, y); data[x] += data[y]; data[y] = x; } return x != y; } bool findSet(int x, int y) { return root(x) == root(y); } int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); } int size(int x) { return -data[root(x)]; } }; const ll MOD = 1000000007; class ModInt{ public: ll v; ModInt(ll _v = 0){ v = _v; } ModInt operator+(ll n){ return ModInt((v+n)%MOD); } ModInt operator-(ll n){ return ModInt((v-n+MOD)%MOD); } ModInt operator*(ll n){ return ModInt((v*n)%MOD); } ModInt operator/(ll n){ return ModInt((ModInt(n).inv()*v).v%MOD); } void operator+=(ll n){ v = (v+n)%MOD; } void operator-=(ll n){ v = (v-n+MOD)%MOD; } void operator*=(ll n){ v = (v*n)%MOD; } ModInt operator+(ModInt n){ return ModInt((v+n.v)%MOD); } ModInt operator-(ModInt n){ return ModInt((v-n.v+MOD)%MOD); } ModInt operator*(ModInt n){ return ModInt((v*n.v)%MOD); } ModInt operator/(ModInt n){ return ModInt((n.inv()*v).v%MOD); } void operator+=(ModInt n){ v = (v+n.v)%MOD; } void operator-=(ModInt n){ v = (v-n.v+MOD)%MOD; } void operator*=(ModInt n){ v = (v*n.v)%MOD; } void operator=(ModInt n){ v = n.v; } void operator=(ll n){ v = n; } ModInt inv(){ if(v == 1) return ModInt(1); else return ModInt(MOD-ModInt(MOD%v).inv().v*(MOD/v)%MOD); } }; ostream& operator<<(ostream& os, const ModInt& m){ os << m.v; return os; } istream & operator >> (istream &in, ModInt &m){ in >> m.v; return in; } ModInt pow(ModInt a, ll n) { ModInt ans = 1; ModInt tmp = a; for (int i = 0; i <= 60; i++) { ll m = (ll)1 << i; if (m & n) { ans *= tmp; } tmp *= tmp; } return ans; } ll N, M, X; ModInt ans = 0; int x[200000], y[200000], z[200000]; bool used[200000]; int depth[200000]; int ch[200000]; vector<int> G[200000]; bool used_dfs[200000]; void dfs(int v){ used_dfs[v] = true; ch[v] = 1; for(int to: G[v]){ if(!used_dfs[to]) { dfs(to); ch[v] += ch[to]; } } } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout << setprecision(10) << fixed; cin >> N >> M >> X; UnionFind uf(N); for(int i = 0; i < M; i++){ cin >> x[i] >> y[i] >> z[i]; x[i]--; y[i]--; int rx = uf.root(x[i]), ry = uf.root(y[i]); if(rx != ry){ used[i] = true; G[x[i]].push_back(y[i]); G[y[i]].push_back(x[i]); uf.unionSet(x[i], y[i]); } } dfs(0); for(int i = 0; i < M; i++){ if(used[i]){ if(ch[x[i]] > ch[y[i]]) swap(x[i], y[i]); ans += pow(X, z[i])*ch[x[i]]*(N-ch[x[i]]); } } cout << ans << endl; }