結果
問題 | No.1207 グラフX |
ユーザー |
![]() |
提出日時 | 2020-07-31 10:56:53 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 387 ms / 2,000 ms |
コード長 | 6,255 bytes |
コンパイル時間 | 1,356 ms |
コンパイル使用メモリ | 131,552 KB |
実行使用メモリ | 34,596 KB |
最終ジャッジ日時 | 2024-07-05 23:16:29 |
合計ジャッジ時間 | 18,590 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 46 |
ソースコード
#line 2 "/Users/kaage/Desktop/ProgrammingWorkspace/library/other/template.hpp"#define _CRT_SECURE_NO_WARNINGS#pragma target("avx")#pragma optimize("O3")#pragma optimize("unroll-loops")#include <algorithm>#include <bitset>#include <cassert>#include <cfloat>#include <climits>#include <cmath>#include <complex>#include <ctime>#include <deque>#include <fstream>#include <functional>#include <iomanip>#include <iostream>#include <iterator>#include <list>#include <map>#include <memory>#include <queue>#include <random>#include <set>#include <stack>#include <string>#include <unordered_map>#include <unordered_set>#include <utility>#include <vector>#define rep(i,n) for(int i=0;i<(lint)(n);i++)#define REP(i,n) for(int i=1;i<=(lint)(n);i++)#define all(V) V.begin(),V.end()typedef long long lint;typedef unsigned long long ulint;typedef std::pair<int, int> P;typedef std::pair<lint, lint> LP;constexpr int INF = INT_MAX/2;constexpr lint LINF = LLONG_MAX/2;constexpr double eps = DBL_EPSILON;constexpr double PI=3.141592653589793238462643383279;template<class T>class prique :public std::priority_queue<T, std::vector<T>, std::greater<T>> {};template <class T, class U>inline bool chmax(T& lhs, const U& rhs) {if (lhs < rhs) {lhs = rhs;return 1;}return 0;}template <class T, class U>inline bool chmin(T& lhs, const U& rhs) {if (lhs > rhs) {lhs = rhs;return 1;}return 0;}inline lint gcd(lint a, lint b) {while (b) {lint c = a;a = b; b = c % b;}return a;}inline lint lcm(lint a, lint b) {return a / gcd(a, b) * b;}bool isprime(lint n) {if (n == 1)return false;for (int i = 2; i * i <= n; i++) {if (n % i == 0)return false;}return true;}template<typename T>T mypow(T a, lint b) {if (!b)return T(1);if (b & 1)return mypow(a, b - 1) * a;T memo = mypow(a, b >> 1);return memo * memo;}lint modpow(lint a, lint b, lint m) {if (!b)return 1;if (b & 1)return modpow(a, b - 1, m) * a % m;lint memo = modpow(a, b >> 1, m);return memo * memo % m;}template<typename T>void printArray(std::vector<T>& vec) {rep(i, vec.size() - 1)std::cout << vec[i] << " ";std::cout << vec.back() << std::endl;}template<typename T>void printArray(T l, T r) {T rprev = r;rprev--;for (T i = l; i != rprev; i++) {std::cout << *i << " ";}std::cout << *rprev << std::endl;}#line 3 "/Users/kaage/Desktop/ProgrammingWorkspace/library/graph/UnionFind.hpp"class UnionFind {protected:std::vector<int> par, rank, size;public:UnionFind(unsigned int size) {par.resize(size); rank.resize(size, 0); this->size.resize(size, 1);rep(i, size) {par[i] = i;}}int find(int n) {if (par[n] == n)return n;return par[n] = find(par[n]);}void unite(int n, int m) {n = find(n);m = find(m);if (n == m)return;if (rank[n] < rank[m]) {par[n] = m;size[m] += size[n];}else {par[m] = n;size[n] += size[m];if (rank[n] == rank[m])rank[n]++;}}bool same(int n, int m) {return find(n) == find(m);}int getsize(int n) {return size[find(n)];}};#line 3 "/Users/kaage/Desktop/ProgrammingWorkspace/library/algebraic/ModInt.hpp"class ModInt {lint value;public:static const unsigned int modulo;ModInt() : value(0) {}template<typename T>ModInt(T value = 0) : value(value) {if (value < 0)value = -(lint)(-value % modulo) + modulo;this->value = value % modulo;}inline operator int()const { return value; }inline ModInt& operator+=(const ModInt& x) {value += x.value;if (value >= modulo)value -= modulo;return *this;}inline ModInt& operator++() {if (value == modulo - 1)value = 0;else value++;return *this;}inline ModInt operator-()const {return ModInt(0) -= *this;}inline ModInt& operator-=(const ModInt& x) {value -= x.value;if (value < 0)value += modulo;return *this;}inline ModInt& operator--() {if (value == 0)value = modulo - 1;else value--;return *this;}inline ModInt& operator*=(const ModInt& x) {value = value * x.value % modulo;return *this;}inline ModInt& operator/=(ModInt rhs) {int exp = modulo - 2;while (exp) {if (exp & 1)*this *= rhs;rhs *= rhs;exp >>= 1;}return *this;}template<typename T> ModInt operator+(const T& rhs)const { return ModInt(*this) += rhs; }template<typename T> ModInt& operator+=(const T& rhs) { return operator+=(ModInt(rhs)); }template<typename T> ModInt operator-(const T& rhs)const { return ModInt(*this) -= rhs; }template<typename T> ModInt& operator-=(const T& rhs) { return operator-=(ModInt(rhs)); }template<typename T> ModInt operator*(const T& rhs)const { return ModInt(*this) *= rhs; }template<typename T> ModInt& operator*=(const T& rhs) { return operator*=(ModInt(rhs)); }template<typename T> ModInt operator/(const T& rhs)const { return ModInt(*this) /= rhs; }template<typename T> ModInt& operator/=(const T& rhs) { return operator/=(ModInt(rhs)); }};std::istream& operator>>(std::istream& ist, ModInt& x) {lint a;ist >> a;x = a;return ist;}#line 4 "main.cpp"const unsigned int ModInt::modulo=1000000007;int n,m,x;ModInt ans;std::vector<std::pair<int,P>> vec;std::vector<P> edges[200010];bool used[200010];int dfs(int node){used[node]=true;int cnt=1;for(const P& i:edges[node]){if(!used[i.first]){int s=dfs(i.first);ans+=mypow(ModInt(x),i.second)*s*(n-s);cnt+=s;}}return cnt;}int main(){std::cin>>n>>m>>x;rep(i,m){int a,b,c;std::cin>>a>>b>>c;vec.push_back({c,{a,b}});}UnionFind uf(n+1);for(const auto& i:vec){if(!uf.same(i.second.first,i.second.second)){uf.unite(i.second.first,i.second.second);edges[i.second.first].emplace_back(i.second.second,i.first);edges[i.second.second].emplace_back(i.second.first,i.first);}}dfs(1);std::cout<<ans<<std::endl;}