結果
問題 | No.1207 グラフX |
ユーザー | Chanyuh |
提出日時 | 2020-08-30 14:24:02 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 233 ms / 2,000 ms |
コード長 | 4,719 bytes |
コンパイル時間 | 1,271 ms |
コンパイル使用メモリ | 137,472 KB |
実行使用メモリ | 37,860 KB |
最終ジャッジ日時 | 2024-04-27 07:28:44 |
合計ジャッジ時間 | 9,439 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 159 ms
21,180 KB |
testcase_01 | AC | 157 ms
21,188 KB |
testcase_02 | AC | 160 ms
21,044 KB |
testcase_03 | AC | 165 ms
21,264 KB |
testcase_04 | AC | 162 ms
21,216 KB |
testcase_05 | AC | 220 ms
37,860 KB |
testcase_06 | AC | 227 ms
37,828 KB |
testcase_07 | AC | 233 ms
37,704 KB |
testcase_08 | AC | 120 ms
15,900 KB |
testcase_09 | AC | 130 ms
18,456 KB |
testcase_10 | AC | 230 ms
30,788 KB |
testcase_11 | AC | 229 ms
37,832 KB |
testcase_12 | AC | 125 ms
16,732 KB |
testcase_13 | AC | 64 ms
10,280 KB |
testcase_14 | AC | 155 ms
20,664 KB |
testcase_15 | AC | 134 ms
17,840 KB |
testcase_16 | AC | 59 ms
10,868 KB |
testcase_17 | AC | 100 ms
15,248 KB |
testcase_18 | AC | 81 ms
15,336 KB |
testcase_19 | AC | 90 ms
13,132 KB |
testcase_20 | AC | 149 ms
20,848 KB |
testcase_21 | AC | 12 ms
8,144 KB |
testcase_22 | AC | 100 ms
15,412 KB |
testcase_23 | AC | 105 ms
16,712 KB |
testcase_24 | AC | 70 ms
14,616 KB |
testcase_25 | AC | 142 ms
20,844 KB |
testcase_26 | AC | 115 ms
17,372 KB |
testcase_27 | AC | 134 ms
19,284 KB |
testcase_28 | AC | 129 ms
18,520 KB |
testcase_29 | AC | 128 ms
19,168 KB |
testcase_30 | AC | 68 ms
12,444 KB |
testcase_31 | AC | 51 ms
9,624 KB |
testcase_32 | AC | 57 ms
12,732 KB |
testcase_33 | AC | 59 ms
12,488 KB |
testcase_34 | AC | 119 ms
17,724 KB |
testcase_35 | AC | 13 ms
8,324 KB |
testcase_36 | AC | 130 ms
18,016 KB |
testcase_37 | AC | 105 ms
16,044 KB |
testcase_38 | AC | 30 ms
9,964 KB |
testcase_39 | AC | 64 ms
13,328 KB |
testcase_40 | AC | 39 ms
8,496 KB |
testcase_41 | AC | 81 ms
12,924 KB |
testcase_42 | AC | 4 ms
8,188 KB |
testcase_43 | AC | 3 ms
8,152 KB |
testcase_44 | AC | 3 ms
8,220 KB |
testcase_45 | AC | 145 ms
21,188 KB |
testcase_46 | AC | 145 ms
21,184 KB |
testcase_47 | AC | 149 ms
21,276 KB |
testcase_48 | AC | 144 ms
21,980 KB |
ソースコード
#include<iostream> #include<string> #include<cstdio> #include<vector> #include<cmath> #include<algorithm> #include<functional> #include<iomanip> #include<queue> #include<ciso646> #include<random> #include<map> #include<set> #include<complex> #include<bitset> #include<stack> #include<unordered_map> #include<utility> #include<tuple> #include<cassert> using namespace std; typedef long long ll; typedef unsigned int ui; const ll mod = 1000000007; const ll INF = (ll)1000000007 * 1000000007; #define stop char nyaa;cin>>nyaa; #define rep(i,n) for(int i=0;i<n;i++) #define per(i,n) for(int i=n-1;i>=0;i--) #define Rep(i,sta,n) for(int i=sta;i<n;i++) #define Per(i,sta,n) for(int i=n-1;i>=sta;i--) #define rep1(i,n) for(int i=1;i<=n;i++) #define per1(i,n) for(int i=n;i>=1;i--) #define Rep1(i,sta,n) for(int i=sta;i<=n;i++) typedef long double ld; const ld eps = 1e-8; const ld pi = acos(-1.0); typedef pair<ll, ll> LP; int dx[4]={1,-1,0,0}; int dy[4]={0,0,1,-1}; struct UnionFind { private: vector<int> par,ran; vector<int> edge,size; int n; public: UnionFind(int x){ n=x; par.resize(n,0); ran.resize(n,0); edge.resize(n,0); size.resize(n,1); rep(i,n){ par[i]=i; } } int find(int x) { if (par[x]==x)return x; else return par[x]=find(par[x]); } void unite(int x, int y) { x=find(x),y=find(y); if (x==y){ edge[x]++; return; } if (ran[x]<ran[y]) { par[x]=y; size[y]+=size[x]; edge[y]+=edge[x]+1; } else { par[y]=x; size[x]+=size[y]; edge[x]+=edge[y]+1; if (ran[x]==ran[y])ran[x]++; } } bool same(int x,int y) { return find(x)==find(y); } int getSize(int x){ return size[find(x)]; } int getEdge(int x){ return edge[find(x)]; } }; template<int mod> struct ModInt { long long x; ModInt() : x(0) {} ModInt(long long y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {} explicit operator int() const {return x;} ModInt &operator+=(const ModInt &p) { if((x += p.x) >= mod) x -= mod; return *this; } ModInt &operator-=(const ModInt &p) { if((x += mod - p.x) >= mod) x -= mod; return *this; } ModInt &operator*=(const ModInt &p) { x = (int)(1LL * x * p.x % mod); return *this; } ModInt &operator/=(const ModInt &p) { *this *= p.inverse(); return *this; } ModInt operator-() const { return ModInt(-x); } ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; } ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; } ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; } ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; } bool operator==(const ModInt &p) const { return x == p.x; } bool operator!=(const ModInt &p) const { return x != p.x; } ModInt inverse() const{ int a = x, b = mod, u = 1, v = 0, t; while(b > 0) { t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } return ModInt(u); } ModInt power(long long p) const{ int a = x; if (p==0) return 1; if (p==1) return ModInt(a); if (p%2==1) return (ModInt(a)*ModInt(a)).power(p/2)*ModInt(a); else return (ModInt(a)*ModInt(a)).power(p/2); } ModInt power(const ModInt p) const{ return ((ModInt)x).power(p.x); } friend ostream &operator<<(ostream &os, const ModInt<mod> &p) { return os << p.x; } friend istream &operator>>(istream &is, ModInt<mod> &a) { long long x; is >> x; a = ModInt<mod>(x); return (is); } }; using modint = ModInt<mod>; typedef pair<int, modint> P; int n,m; modint x; vector<P> G[200010]; int siz[200010]; modint ans=0; void dfs(int s,int par){ siz[s]=1; for(P p:G[s]){ int t=p.first;modint z=p.second; if(t==par) continue; dfs(t,s); siz[s]+=siz[t]; ans+=(modint)siz[t]*(modint)(n-siz[t])*z; } } void solve(){ cin >> n >> m; cin >> x; UnionFind uf(n); rep(i,m){ int a,b,c;cin >> a >> b >> c;a--;b--; if(uf.same(a,b)) continue; uf.unite(a,b); modint z=x.power(c); G[a].push_back(P(b,z)); G[b].push_back(P(a,z)); } dfs(0,-1); cout << ans << endl; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(50); solve(); }