結果
問題 | No.1207 グラフX |
ユーザー |
![]() |
提出日時 | 2020-08-30 13:57:34 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 383 ms / 2,000 ms |
コード長 | 3,317 bytes |
コンパイル時間 | 1,220 ms |
コンパイル使用メモリ | 105,244 KB |
実行使用メモリ | 36,804 KB |
最終ジャッジ日時 | 2024-11-15 07:09:21 |
合計ジャッジ時間 | 15,643 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 46 |
ソースコード
#include<iostream>#include<cstdio>#include<cstring>#include<string>#include<vector>#include<cmath>#include<algorithm>#include<map>#include<queue>#include<deque>#include<iomanip>#include<tuple>#include<cassert>#include<set>using namespace std;typedef long long int LL;typedef pair<int,int> P;typedef pair<LL,int> LP;const int INF=1<<30;const LL MAX=1e9+7;void array_show(int *array,int array_n,char middle=' '){for(int i=0;i<array_n;i++)printf("%d%c",array[i],(i!=array_n-1?middle:'\n'));}void array_show(LL *array,int array_n,char middle=' '){for(int i=0;i<array_n;i++)printf("%lld%c",array[i],(i!=array_n-1?middle:'\n'));}void array_show(vector<int> &vec_s,int vec_n=-1,char middle=' '){if(vec_n==-1)vec_n=vec_s.size();for(int i=0;i<vec_n;i++)printf("%d%c",vec_s[i],(i!=vec_n-1?middle:'\n'));}void array_show(vector<LL> &vec_s,int vec_n=-1,char middle=' '){if(vec_n==-1)vec_n=vec_s.size();for(int i=0;i<vec_n;i++)printf("%lld%c",vec_s[i],(i!=vec_n-1?middle:'\n'));}class union_find_tree{private:static constexpr int uft_N=100005;int uft_n;queue<int> uft_q1;vector<int> uft_parent;vector<int> uft_num;public:void init(){uft_parent.assign(uft_n,-1);uft_num.assign(uft_n,1);}union_find_tree(int uft_n_init){assert(uft_n_init>=0);uft_n=uft_n_init;init();}union_find_tree(){uft_n=uft_N;init();}int check_parent(int uft_x){assert(uft_x>=0 && uft_x<uft_n);if(uft_parent[uft_x]!=-1){uft_q1.push(uft_x);return check_parent(uft_parent[uft_x]);}int uft_a;while(!uft_q1.empty()){uft_a=uft_q1.front(),uft_q1.pop();uft_parent[uft_a]=uft_x;}return uft_x;}bool connect(int uft_x,int uft_y){assert(uft_x>=0 && uft_x<uft_n);assert(uft_y>=0 && uft_y<uft_n);uft_x=check_parent(uft_x),uft_y=check_parent(uft_y);if(uft_x==uft_y)return true;if(uft_num[uft_x]>uft_num[uft_y])swap(uft_x,uft_y);uft_parent[uft_x]=uft_y;uft_num[uft_y]+=uft_num[uft_x];return false;}int size(int pos){pos=check_parent(pos);return uft_num[pos];}};long long int pow_mod(long long int p_a,long long int p_n,long long int p_p=1e9+7){//p_a^p_n mod p_plong long int p_b=1,p_t=1;for(;p_b<=p_n;p_b<<=1);for(p_b>>=1;p_b>0;p_b>>=1){p_t*=p_t;if(p_t>=p_p)p_t%=p_p;if(p_n&p_b)p_t*=p_a;if(p_t>=p_p)p_t%=p_p;}return p_t;}LL n,m,p;vector<P> path[220000];LL sz[220000];LL check(int pos,int bef){LL s=0;LL a=0;for(auto node:path[pos]){if(node.first==bef)continue;s+=check(node.first,pos);a+=sz[node.first];s+=sz[node.first]*(n-sz[node.first])%MAX*pow_mod(p,node.second)%MAX;}sz[pos]=a+1;s%=MAX;return s;}int main(){int i,j,k;int a,b,c;cin>>n>>m>>p;union_find_tree ua(n);for(i=0;i<m;i++){cin>>a>>b>>c;a--,b--;if(ua.connect(a,b))continue;path[a].push_back(make_pair(b,c));path[b].push_back(make_pair(a,c));}cout<<check(0,-1)<<endl;}