結果
問題 | No.1207 グラフX |
ユーザー | msm1993 |
提出日時 | 2020-10-08 10:12:30 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 201 ms / 2,000 ms |
コード長 | 3,802 bytes |
コンパイル時間 | 2,725 ms |
コンパイル使用メモリ | 174,140 KB |
実行使用メモリ | 27,272 KB |
最終ジャッジ日時 | 2023-09-27 11:42:51 |
合計ジャッジ時間 | 11,241 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 131 ms
16,328 KB |
testcase_01 | AC | 132 ms
16,380 KB |
testcase_02 | AC | 133 ms
16,580 KB |
testcase_03 | AC | 128 ms
16,352 KB |
testcase_04 | AC | 128 ms
16,344 KB |
testcase_05 | AC | 170 ms
27,192 KB |
testcase_06 | AC | 201 ms
27,252 KB |
testcase_07 | AC | 174 ms
27,268 KB |
testcase_08 | AC | 106 ms
10,792 KB |
testcase_09 | AC | 115 ms
13,632 KB |
testcase_10 | AC | 158 ms
21,384 KB |
testcase_11 | AC | 169 ms
27,272 KB |
testcase_12 | AC | 97 ms
11,444 KB |
testcase_13 | AC | 58 ms
5,192 KB |
testcase_14 | AC | 127 ms
15,716 KB |
testcase_15 | AC | 104 ms
12,916 KB |
testcase_16 | AC | 53 ms
5,760 KB |
testcase_17 | AC | 84 ms
10,228 KB |
testcase_18 | AC | 73 ms
10,476 KB |
testcase_19 | AC | 79 ms
7,436 KB |
testcase_20 | AC | 126 ms
16,272 KB |
testcase_21 | AC | 10 ms
4,380 KB |
testcase_22 | AC | 82 ms
10,524 KB |
testcase_23 | AC | 99 ms
11,708 KB |
testcase_24 | AC | 63 ms
9,628 KB |
testcase_25 | AC | 120 ms
16,044 KB |
testcase_26 | AC | 95 ms
12,340 KB |
testcase_27 | AC | 129 ms
14,528 KB |
testcase_28 | AC | 117 ms
13,728 KB |
testcase_29 | AC | 111 ms
14,368 KB |
testcase_30 | AC | 56 ms
7,416 KB |
testcase_31 | AC | 49 ms
4,392 KB |
testcase_32 | AC | 48 ms
7,692 KB |
testcase_33 | AC | 53 ms
7,536 KB |
testcase_34 | AC | 118 ms
12,592 KB |
testcase_35 | AC | 12 ms
4,376 KB |
testcase_36 | AC | 110 ms
13,436 KB |
testcase_37 | AC | 90 ms
10,896 KB |
testcase_38 | AC | 24 ms
5,060 KB |
testcase_39 | AC | 57 ms
8,384 KB |
testcase_40 | AC | 38 ms
4,380 KB |
testcase_41 | AC | 74 ms
7,788 KB |
testcase_42 | AC | 1 ms
4,380 KB |
testcase_43 | AC | 2 ms
4,380 KB |
testcase_44 | AC | 1 ms
4,376 KB |
testcase_45 | AC | 129 ms
16,420 KB |
testcase_46 | AC | 128 ms
16,464 KB |
testcase_47 | AC | 119 ms
16,468 KB |
testcase_48 | AC | 128 ms
16,368 KB |
ソースコード
#include <bits/stdc++.h> #define rep(i,n) for (int i = 0; i < (int)(n); i ++) #define irep(i,n) for (int i = (int)(n) - 1;i >= 0;--i) using namespace std; using ll = long long; using PL = pair<ll,ll>; using P = pair<int,int>; constexpr int INF = 1000000000; constexpr long long HINF = 1000000000000000; constexpr long long MOD = 1000000007;// = 998244353; constexpr double EPS = 1e-4; constexpr double PI = 3.14159265358979; struct UnionFind { int N; vector<int> parents; UnionFind(int _N) : N(_N){ parents.assign(N,-1); } int find(int x) { //xの親を返す if (parents[x] < 0) return x; return parents[x] = find(parents[x]); } void unite(int x, int y) { //xとyの含むグループを併合 int px = find(x); int py = find(y); if (parents[px] > parents[py]) swap(px,py); if (px != py) { parents[px] += parents[py]; parents[py] = px; } } bool same(int x, int y) { //x,yが同じグループにいるか判定 return find(x) == find(y); } int size(int x) { //xと同じグループのメンバーの個数 return -parents[find(x)]; } vector<int> root() {//ufの根を列挙 vector<int> res; for (int i = 0; i < N; i ++) { if (parents[i] < 0) res.push_back(i); } return res; } int group_count() { //ufのグループの数を数える int cnt = 0; for (int i = 0; i < N; i ++) { if (parents[i] < 0) cnt ++; } return cnt; } }; template<int Modulus> struct ModInt { long long x; ModInt(long long x = 0) :x((x%Modulus + Modulus)%Modulus) {} constexpr ModInt &operator+=(const ModInt a) {if ((x += a.x) >= Modulus) x -= Modulus; return *this;} constexpr ModInt &operator-=(const ModInt a) {if ((x += Modulus - a.x) >= Modulus) x -= Modulus; return *this;} constexpr ModInt &operator*=(const ModInt a) {(x *= a.x) %= Modulus; return *this;} constexpr ModInt &operator/=(const ModInt a) {return *this *= a.inverse();} constexpr ModInt operator+(const ModInt a) const {return ModInt(*this) += a.x;} constexpr ModInt operator-(const ModInt a) const {return ModInt(*this) -= a.x;} constexpr ModInt operator*(const ModInt a) const {return ModInt(*this) *= a.x;} constexpr ModInt operator/(const ModInt a) const {return ModInt(*this) /= a.x;} friend constexpr ostream& operator<<(ostream& os,const ModInt<Modulus>& a) {return os << a.x;} friend constexpr istream& operator>>(istream& is,ModInt<Modulus>& a) {return is >> a.x;} ModInt inverse() const {// x ^ (-1) long long a = x,b = Modulus,p = 1,q = 0; while (b) {long long d = a/b; a -= d*b; swap(a,b); p -= d*q; swap(p,q);} return ModInt(p); } ModInt pow(long long N) {// x ^ N ModInt a = 1; while (N) { if (N&1) a *= *this; *this *= *this; N >>= 1; } return a; } }; using mint = ModInt<1000000007>; mint ans = 0; int N; ll X; vector<vector<P>> G; int dfs(int v,int pa = -1) { int cnt = 1; for (const P &p:G[v]) { if (p.first == pa) continue; int c = dfs(p.first,v); ans += mint(N - c) * mint(c) * mint(X).pow(p.second); cnt += c; } return cnt; } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int M; cin >> N >> M >> X; UnionFind uf(N); G.resize(N); rep(i,M) { int a,b,c; cin >> a >> b >> c; --a; --b; if (uf.same(a,b)) continue; uf.unite(a,b); G[a].emplace_back(b,c); G[b].emplace_back(a,c); } dfs(0); cout << ans << '\n'; return 0; }