結果
問題 | No.1207 グラフX |
ユーザー | Chanyuh |
提出日時 | 2020-08-30 14:24:02 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 272 ms / 2,000 ms |
コード長 | 4,719 bytes |
コンパイル時間 | 1,658 ms |
コンパイル使用メモリ | 135,012 KB |
実行使用メモリ | 37,704 KB |
最終ジャッジ日時 | 2023-08-09 12:24:57 |
合計ジャッジ時間 | 11,582 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 212 ms
21,060 KB |
testcase_01 | AC | 212 ms
21,204 KB |
testcase_02 | AC | 203 ms
21,080 KB |
testcase_03 | AC | 201 ms
21,080 KB |
testcase_04 | AC | 204 ms
21,084 KB |
testcase_05 | AC | 270 ms
37,504 KB |
testcase_06 | AC | 261 ms
37,616 KB |
testcase_07 | AC | 270 ms
37,704 KB |
testcase_08 | AC | 142 ms
15,956 KB |
testcase_09 | AC | 155 ms
18,376 KB |
testcase_10 | AC | 260 ms
30,760 KB |
testcase_11 | AC | 272 ms
37,644 KB |
testcase_12 | AC | 146 ms
16,524 KB |
testcase_13 | AC | 68 ms
10,392 KB |
testcase_14 | AC | 194 ms
20,480 KB |
testcase_15 | AC | 162 ms
17,528 KB |
testcase_16 | AC | 67 ms
10,784 KB |
testcase_17 | AC | 122 ms
15,096 KB |
testcase_18 | AC | 100 ms
15,260 KB |
testcase_19 | AC | 100 ms
12,652 KB |
testcase_20 | AC | 187 ms
20,856 KB |
testcase_21 | AC | 13 ms
8,228 KB |
testcase_22 | AC | 113 ms
15,228 KB |
testcase_23 | AC | 134 ms
16,436 KB |
testcase_24 | AC | 95 ms
14,540 KB |
testcase_25 | AC | 183 ms
20,624 KB |
testcase_26 | AC | 145 ms
17,368 KB |
testcase_27 | AC | 170 ms
19,016 KB |
testcase_28 | AC | 162 ms
18,228 KB |
testcase_29 | AC | 167 ms
18,940 KB |
testcase_30 | AC | 76 ms
12,384 KB |
testcase_31 | AC | 57 ms
9,556 KB |
testcase_32 | AC | 70 ms
12,608 KB |
testcase_33 | AC | 72 ms
12,412 KB |
testcase_34 | AC | 154 ms
17,428 KB |
testcase_35 | AC | 15 ms
8,360 KB |
testcase_36 | AC | 148 ms
17,964 KB |
testcase_37 | AC | 121 ms
15,788 KB |
testcase_38 | AC | 31 ms
9,784 KB |
testcase_39 | AC | 70 ms
13,216 KB |
testcase_40 | AC | 40 ms
8,628 KB |
testcase_41 | AC | 97 ms
12,820 KB |
testcase_42 | AC | 4 ms
8,028 KB |
testcase_43 | AC | 5 ms
8,116 KB |
testcase_44 | AC | 4 ms
8,128 KB |
testcase_45 | AC | 195 ms
21,116 KB |
testcase_46 | AC | 183 ms
21,052 KB |
testcase_47 | AC | 189 ms
21,020 KB |
testcase_48 | AC | 183 ms
21,348 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(); }