結果

問題 No.1207 グラフX
ユーザー 沙耶花
提出日時 2020-08-30 13:23:58
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 468 ms / 2,000 ms
コード長 1,500 bytes
コンパイル時間 2,522 ms
コンパイル使用メモリ 201,884 KB
最終ジャッジ日時 2025-01-13 21:06:37
ジャッジサーバーID
(参考情報)
judge5 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 46
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:60:9: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’
   60 | int dfs(auto &E,int now,int p){
      |         ^~~~

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
#define modulo 1000000007
#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)
#define Inf 1000000000
struct unionfind{
vector<int> data;
vector<int> size;
unionfind(int n){
for(int i=0;i<n;i++){
data.push_back(i);
size.push_back(1);
}
}
int find(int x){
if(data[x]==x)return x;
return data[x]=find(data[x]);
}
bool unite(int x,int y){
x=find(x);y=find(y);
if(x==y)return false;
if(size[x]>size[y])swap(x,y);
data[x]=y;
size[y]+=size[x];
return true;
}
bool check(int x,int y){
return (find(x)==find(y));
}
int get_size(int x){
int X = find(x);
return size[X];
}
};
int beki(long long a,long long b,int M = modulo){
int x = 1;
while(b!=0){
if(b&1){
x=((long long)x*a)%M;
}
a=((long long)a*a)%M;
b>>=1;
}
return x;
}
int gyakugen(int a){
return beki(a,modulo-2);
}
int N,M,X;
int ans = 0;
int dfs(auto &E,int now,int p){
int ret = 0;
for(int i=0;i<E[now].size();i++){
int to = E[now][i].first;
int z = E[now][i].second;
if(to==p)continue;
int t = dfs(E,to,now);
int Y = mod(t*(N-t));
ans = mod(ans + mod(beki(X,z)*Y));
ret += t;
}
return ret+1;
}
int main(){
cin>>N>>M>>X;
vector<vector<pair<int,int>>> E(N,vector<pair<int,int>>());
unionfind uf(N);
for(int i=0;i<M;i++){
int x,y,z;
cin>>x>>y>>z;
x--;y--;
if(uf.unite(x,y)){
E[x].emplace_back(y,z);
E[y].emplace_back(x,z);
}
}
dfs(E,0,-1);
cout<<ans<<endl;
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0