結果
問題 | No.1207 グラフX |
ユーザー | moririn2528_c |
提出日時 | 2020-08-30 13:57:34 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 372 ms / 2,000 ms |
コード長 | 3,317 bytes |
コンパイル時間 | 1,047 ms |
コンパイル使用メモリ | 105,080 KB |
実行使用メモリ | 36,800 KB |
最終ジャッジ日時 | 2024-04-27 07:13:20 |
合計ジャッジ時間 | 15,420 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 322 ms
19,516 KB |
testcase_01 | AC | 318 ms
19,532 KB |
testcase_02 | AC | 312 ms
19,476 KB |
testcase_03 | AC | 316 ms
19,372 KB |
testcase_04 | AC | 323 ms
19,360 KB |
testcase_05 | AC | 372 ms
36,672 KB |
testcase_06 | AC | 369 ms
36,456 KB |
testcase_07 | AC | 365 ms
36,800 KB |
testcase_08 | AC | 269 ms
15,384 KB |
testcase_09 | AC | 284 ms
16,668 KB |
testcase_10 | AC | 362 ms
28,100 KB |
testcase_11 | AC | 364 ms
36,676 KB |
testcase_12 | AC | 260 ms
15,700 KB |
testcase_13 | AC | 172 ms
10,324 KB |
testcase_14 | AC | 307 ms
18,948 KB |
testcase_15 | AC | 278 ms
16,896 KB |
testcase_16 | AC | 162 ms
11,992 KB |
testcase_17 | AC | 213 ms
14,768 KB |
testcase_18 | AC | 176 ms
15,148 KB |
testcase_19 | AC | 237 ms
12,612 KB |
testcase_20 | AC | 320 ms
19,236 KB |
testcase_21 | AC | 35 ms
9,156 KB |
testcase_22 | AC | 212 ms
14,592 KB |
testcase_23 | AC | 233 ms
16,148 KB |
testcase_24 | AC | 153 ms
14,612 KB |
testcase_25 | AC | 305 ms
19,160 KB |
testcase_26 | AC | 244 ms
16,664 KB |
testcase_27 | AC | 291 ms
18,064 KB |
testcase_28 | AC | 276 ms
17,236 KB |
testcase_29 | AC | 270 ms
18,048 KB |
testcase_30 | AC | 150 ms
12,612 KB |
testcase_31 | AC | 154 ms
10,052 KB |
testcase_32 | AC | 124 ms
12,996 KB |
testcase_33 | AC | 135 ms
12,060 KB |
testcase_34 | AC | 275 ms
16,376 KB |
testcase_35 | AC | 35 ms
8,820 KB |
testcase_36 | AC | 262 ms
16,904 KB |
testcase_37 | AC | 236 ms
14,836 KB |
testcase_38 | AC | 64 ms
10,216 KB |
testcase_39 | AC | 136 ms
12,572 KB |
testcase_40 | AC | 131 ms
9,412 KB |
testcase_41 | AC | 210 ms
12,364 KB |
testcase_42 | AC | 4 ms
9,284 KB |
testcase_43 | AC | 4 ms
9,540 KB |
testcase_44 | AC | 3 ms
8,772 KB |
testcase_45 | AC | 285 ms
19,348 KB |
testcase_46 | AC | 281 ms
19,544 KB |
testcase_47 | AC | 284 ms
19,504 KB |
testcase_48 | AC | 280 ms
19,480 KB |
ソースコード
#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_p long 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; }