結果
問題 | No.1207 グラフX |
ユーザー | pockyny |
提出日時 | 2020-08-30 17:03:16 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 423 ms / 2,000 ms |
コード長 | 1,535 bytes |
コンパイル時間 | 1,048 ms |
コンパイル使用メモリ | 84,664 KB |
実行使用メモリ | 31,604 KB |
最終ジャッジ日時 | 2023-08-09 16:30:56 |
合計ジャッジ時間 | 17,465 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 351 ms
20,320 KB |
testcase_01 | AC | 365 ms
20,252 KB |
testcase_02 | AC | 353 ms
20,276 KB |
testcase_03 | AC | 360 ms
20,304 KB |
testcase_04 | AC | 363 ms
20,412 KB |
testcase_05 | AC | 412 ms
31,580 KB |
testcase_06 | AC | 416 ms
31,604 KB |
testcase_07 | AC | 420 ms
31,604 KB |
testcase_08 | AC | 270 ms
16,012 KB |
testcase_09 | AC | 293 ms
17,740 KB |
testcase_10 | AC | 409 ms
25,960 KB |
testcase_11 | AC | 423 ms
31,444 KB |
testcase_12 | AC | 282 ms
16,588 KB |
testcase_13 | AC | 168 ms
12,308 KB |
testcase_14 | AC | 347 ms
19,676 KB |
testcase_15 | AC | 300 ms
17,436 KB |
testcase_16 | AC | 159 ms
12,652 KB |
testcase_17 | AC | 225 ms
15,488 KB |
testcase_18 | AC | 199 ms
15,816 KB |
testcase_19 | AC | 231 ms
13,712 KB |
testcase_20 | AC | 359 ms
19,976 KB |
testcase_21 | AC | 32 ms
10,800 KB |
testcase_22 | AC | 225 ms
15,572 KB |
testcase_23 | AC | 255 ms
16,620 KB |
testcase_24 | AC | 171 ms
15,244 KB |
testcase_25 | AC | 348 ms
19,704 KB |
testcase_26 | AC | 269 ms
17,236 KB |
testcase_27 | AC | 320 ms
18,544 KB |
testcase_28 | AC | 313 ms
17,632 KB |
testcase_29 | AC | 305 ms
18,616 KB |
testcase_30 | AC | 155 ms
13,568 KB |
testcase_31 | AC | 143 ms
11,700 KB |
testcase_32 | AC | 134 ms
13,932 KB |
testcase_33 | AC | 141 ms
13,676 KB |
testcase_34 | AC | 287 ms
17,512 KB |
testcase_35 | AC | 33 ms
10,908 KB |
testcase_36 | AC | 284 ms
17,824 KB |
testcase_37 | AC | 245 ms
16,000 KB |
testcase_38 | AC | 72 ms
11,972 KB |
testcase_39 | AC | 155 ms
14,036 KB |
testcase_40 | AC | 122 ms
10,976 KB |
testcase_41 | AC | 208 ms
13,736 KB |
testcase_42 | AC | 4 ms
10,800 KB |
testcase_43 | AC | 5 ms
10,756 KB |
testcase_44 | AC | 5 ms
10,748 KB |
testcase_45 | AC | 337 ms
20,288 KB |
testcase_46 | AC | 336 ms
20,396 KB |
testcase_47 | AC | 338 ms
20,240 KB |
testcase_48 | AC | 334 ms
20,232 KB |
ソースコード
#include <iostream> #include <algorithm> #include <vector> using namespace std; int par[200010],sz[200010]; void init(int n){ for(int i=0;i<n;i++){ par[i] = i; sz[i] = 1; } } int find(int x){ if(par[x]==x) return x; return par[x] = find(par[x]); } void unite(int x, int y){ x = find(x); y = find(y); if(x==y) return; if(sz[x]>sz[y]) swap(x,y); par[x] = y; sz[y] += sz[x]; } bool same(int x, int y){ return find(x)==find(y); } typedef long long ll; ll mod = 1000000007; ll pw(ll a,ll x){ ll ret = 1; while(x){ if(x&1) (ret *= a) %= mod; (a *= a) %= mod; x /= 2; } return ret; } pair<int,pair<int,int>> p[200010]; vector<pair<int,int>> G[200010]; int sum[200010] = {}; void dfs(int s,int p){ for(auto v:G[s]){ if(v.first==p) continue; dfs(v.first,s); sum[s] += sum[v.first]; } sum[s]++; } int main(){ int i,n,m,x; cin >> n >> m >> x; for(i=0;i<m;i++){ int a,b,c; cin >> a >> b >> c; a--; b--; p[i] = {c,{a,b}}; } sort(p,p + m); ll ans = 0; init(n); for(i=0;i<m;i++){ int u = p[i].second.first,v = p[i].second.second; if(same(u,v)) continue; unite(u,v); G[u].push_back({v,p[i].first}); G[v].push_back({u,p[i].first}); } dfs(0,-1); for(i=0;i<n;i++){ for(auto q:G[i]){ int u = i,v = q.first; if(sum[u]<sum[v]) continue; (ans += pw(x,q.second)*sum[v]%mod*(n - sum[v])%mod) %= mod; } } cout << ans << endl; }