#544496 (C++17) No.1207 グラフX

提出ソース

結果

問題	No.1207 グラフX
ユーザー	pockyny
提出日時	2020-08-30 17:03:16
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	484 ms / 2,000 ms
コード長	1,535 bytes
コンパイル時間	1,105 ms
コンパイル使用メモリ	84,820 KB
実行使用メモリ	34,732 KB
最終ジャッジ日時	2024-04-27 11:16:24
合計ジャッジ時間	18,625 ms
ジャッジサーバーID （参考情報）	judge5 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	400 ms 20,512 KB
testcase_01	AC	400 ms 20,468 KB
testcase_02	AC	394 ms 20,360 KB
testcase_03	AC	403 ms 20,564 KB
testcase_04	AC	401 ms 20,484 KB
testcase_05	AC	479 ms 34,632 KB
testcase_06	AC	484 ms 34,660 KB
testcase_07	AC	477 ms 34,732 KB
testcase_08	AC	318 ms 16,152 KB
testcase_09	AC	333 ms 17,720 KB
testcase_10	AC	473 ms 27,424 KB
testcase_11	AC	478 ms 34,712 KB
testcase_12	AC	314 ms 16,724 KB
testcase_13	AC	189 ms 11,648 KB
testcase_14	AC	378 ms 20,000 KB
testcase_15	AC	329 ms 17,624 KB
testcase_16	AC	182 ms 12,032 KB
testcase_17	AC	257 ms 15,308 KB
testcase_18	AC	219 ms 14,992 KB
testcase_19	AC	263 ms 13,756 KB
testcase_20	AC	395 ms 20,220 KB
testcase_21	AC	35 ms 8,576 KB
testcase_22	AC	253 ms 15,212 KB
testcase_23	AC	282 ms 16,436 KB
testcase_24	AC	194 ms 14,232 KB
testcase_25	AC	388 ms 20,036 KB
testcase_26	AC	303 ms 17,148 KB
testcase_27	AC	362 ms 18,836 KB
testcase_28	AC	347 ms 17,788 KB
testcase_29	AC	339 ms 18,676 KB
testcase_30	AC	179 ms 12,544 KB
testcase_31	AC	165 ms 11,008 KB
testcase_32	AC	154 ms 12,672 KB
testcase_33	AC	161 ms 12,672 KB
testcase_34	AC	319 ms 17,336 KB
testcase_35	AC	37 ms 8,704 KB
testcase_36	AC	321 ms 17,676 KB
testcase_37	AC	280 ms 15,724 KB
testcase_38	AC	78 ms 10,368 KB
testcase_39	AC	169 ms 13,012 KB
testcase_40	AC	134 ms 10,112 KB
testcase_41	AC	240 ms 13,568 KB
testcase_42	AC	4 ms 8,320 KB
testcase_43	AC	5 ms 8,064 KB
testcase_44	AC	5 ms 8,192 KB
testcase_45	AC	383 ms 20,588 KB
testcase_46	AC	382 ms 20,368 KB
testcase_47	AC	382 ms 20,456 KB
testcase_48	AC	383 ms 20,456 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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;
}

yukicoder

結果

テストケース

ソースコード