結果
問題 | No.1207 グラフX |
ユーザー | RTnF |
提出日時 | 2020-08-30 14:03:24 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 317 ms / 2,000 ms |
コード長 | 7,434 bytes |
コンパイル時間 | 2,662 ms |
コンパイル使用メモリ | 210,540 KB |
実行使用メモリ | 71,860 KB |
最終ジャッジ日時 | 2023-08-09 12:12:02 |
合計ジャッジ時間 | 15,253 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 235 ms
54,040 KB |
testcase_01 | AC | 228 ms
53,964 KB |
testcase_02 | AC | 214 ms
54,060 KB |
testcase_03 | AC | 223 ms
53,732 KB |
testcase_04 | AC | 215 ms
53,692 KB |
testcase_05 | AC | 302 ms
71,860 KB |
testcase_06 | AC | 317 ms
71,720 KB |
testcase_07 | AC | 311 ms
71,772 KB |
testcase_08 | AC | 160 ms
46,512 KB |
testcase_09 | AC | 187 ms
50,448 KB |
testcase_10 | AC | 298 ms
64,656 KB |
testcase_11 | AC | 316 ms
71,716 KB |
testcase_12 | AC | 174 ms
47,664 KB |
testcase_13 | AC | 82 ms
37,764 KB |
testcase_14 | AC | 209 ms
52,976 KB |
testcase_15 | AC | 174 ms
49,088 KB |
testcase_16 | AC | 85 ms
38,724 KB |
testcase_17 | AC | 141 ms
45,352 KB |
testcase_18 | AC | 121 ms
45,440 KB |
testcase_19 | AC | 124 ms
41,960 KB |
testcase_20 | AC | 222 ms
53,692 KB |
testcase_21 | AC | 21 ms
34,732 KB |
testcase_22 | AC | 139 ms
45,596 KB |
testcase_23 | AC | 153 ms
47,156 KB |
testcase_24 | AC | 106 ms
43,908 KB |
testcase_25 | AC | 218 ms
53,220 KB |
testcase_26 | AC | 157 ms
48,600 KB |
testcase_27 | AC | 203 ms
51,448 KB |
testcase_28 | AC | 197 ms
50,264 KB |
testcase_29 | AC | 198 ms
51,468 KB |
testcase_30 | AC | 95 ms
40,980 KB |
testcase_31 | AC | 68 ms
36,712 KB |
testcase_32 | AC | 80 ms
41,408 KB |
testcase_33 | AC | 83 ms
41,372 KB |
testcase_34 | AC | 173 ms
48,848 KB |
testcase_35 | AC | 22 ms
34,936 KB |
testcase_36 | AC | 179 ms
51,132 KB |
testcase_37 | AC | 150 ms
46,324 KB |
testcase_38 | AC | 42 ms
37,232 KB |
testcase_39 | AC | 92 ms
42,088 KB |
testcase_40 | AC | 52 ms
35,208 KB |
testcase_41 | AC | 119 ms
41,980 KB |
testcase_42 | AC | 11 ms
34,644 KB |
testcase_43 | AC | 11 ms
34,640 KB |
testcase_44 | AC | 11 ms
34,636 KB |
testcase_45 | AC | 219 ms
54,728 KB |
testcase_46 | AC | 214 ms
53,884 KB |
testcase_47 | AC | 211 ms
53,992 KB |
testcase_48 | AC | 217 ms
54,436 KB |
ソースコード
#pragma region template #include <bits/stdc++.h> using namespace std; using ll = long long; using ull = unsigned long long; using ld = long double; using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>; using vll = vector<ll>; using vvll = vector<vll>; using vvvll = vector<vvll>; using vld = vector<ld>; using vvld = vector<vld>; using vvvld = vector<vvld>; using vs = vector<string>; using pll = pair<ll, ll>; using vp = vector<pll>; template <typename T> using pqrev = priority_queue<T, vector<T>, greater<T>>; #define rep(i, n) for (ll i = 0, i##_end = (n); i < i##_end; i++) #define repb(i, n) for (ll i = (n)-1; i >= 0; i--) #define repr(i, a, b) for (ll i = (a), i##_end = (b); i < i##_end; i++) #define reprb(i, a, b) for (ll i = (b)-1, i##_end = (a); i >= i##_end; i--) #define ALL(a) (a).begin(), (a).end() #define SZ(x) ((ll)(x).size()) //* constexpr ll MOD = 1e9 + 7; /*/ constexpr ll MOD = 998244353; //*/ constexpr ll INF = 1e+18; constexpr ld EPS = 1e-12L; constexpr ld PI = 3.14159265358979323846L; constexpr ll GCD(ll a, ll b) { return b ? GCD(b, a % b) : a; } constexpr ll LCM(ll a, ll b) { return a / GCD(a, b) * b; } template <typename S, typename T> constexpr bool chmax(S &a, const T &b) { if (a < b) { a = b; return 1; } return 0; } template <typename S, typename T> constexpr bool chmin(S &a, const T &b) { if (b < a) { a = b; return 1; } return 0; } #ifdef OJ_LOCAL #include "dump.hpp" #else #define dump(...) ((void)0) #endif template <typename T> bool print_(const T &a) { cout << a; return true; } template <typename T> bool print_(const vector<T> &vec) { for (auto &a : vec) { cout << a; if (&a != &vec.back()) { cout << " "; } } return false; } template <typename T> bool print_(const vector<vector<T>> &vv) { for (auto &v : vv) { for (auto &a : v) { cout << a; if (&a != &v.back()) { cout << " "; } } if (&v != &vv.back()) { cout << "\n"; } } return false; } void print() { cout << "\n"; } template <typename Head, typename... Tail> void print(Head &&head, Tail &&... tail) { bool f = print_(head); if (sizeof...(tail) != 0) { cout << (f ? " " : "\n"); } print(forward<Tail>(tail)...); } #pragma endregion // ModInt // 参考:https://ei1333.github.io/luzhiled/snippets/math/mod-int.html // modはコンパイル時に決定 template <ll mod> struct ModInt { ll x; ModInt() : x(0) {} ModInt(ll y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {} constexpr ModInt &operator+=(const ModInt &p) { if ((x += p.x) >= mod) x -= mod; return *this; } constexpr ModInt &operator-=(const ModInt &p) { if ((x += mod - p.x) >= mod) x -= mod; return *this; } constexpr ModInt &operator*=(const ModInt &p) { x = x * p.x % mod; return *this; } constexpr ModInt &operator/=(const ModInt &p) { *this *= p.inverse(); return *this; } constexpr ModInt operator-() { return ModInt(-x); } constexpr ModInt operator+(const ModInt &p) { return ModInt(*this) += p; } constexpr ModInt operator-(const ModInt &p) { return ModInt(*this) -= p; } constexpr ModInt operator*(const ModInt &p) { return ModInt(*this) *= p; } constexpr ModInt operator/(const ModInt &p) { return ModInt(*this) /= p; } constexpr bool operator==(const ModInt &p) { return x == p.x; } constexpr bool operator!=(const ModInt &p) { return x != p.x; } constexpr ModInt inverse() const { ll a = x, b = mod, u = 1, v = 0, t; while (b > 0) { t = a / b; swap(a -= t * b, b); swap(u -= t * v, v); } return ModInt(u); } constexpr ModInt pow(ll n) { ModInt ret(1), mul(x); while (n > 0) { if (n & 1) ret *= mul; mul *= mul; n >>= 1; } return ret; } friend ostream &operator<<(ostream &os, const ModInt &p) { return os << p.x; } friend istream &operator>>(istream &is, ModInt &a) { ll t; is >> t; a = ModInt<mod>(t); return (is); } }; using mint = ModInt<MOD>; using vm = vector<mint>; using vvm = vector<vm>; constexpr int MAX_FAC = 2000010; mint fac[MAX_FAC], facinv[MAX_FAC]; void combInit() { fac[0] = mint(1); for (int i = 0; i < MAX_FAC - 1; i++) { fac[i + 1] = fac[i] * (i + 1); } facinv[MAX_FAC - 1] = fac[MAX_FAC - 1].inverse(); for (int i = MAX_FAC - 2; i >= 0; i--) { facinv[i] = facinv[i + 1] * (i + 1); } } mint comb(const ll a, const ll b) { assert(a < MAX_FAC); assert(b < MAX_FAC); if (a < 0 || b < 0 || b > a) { return mint(0); } mint ret(1); ret *= fac[a]; ret *= facinv[b]; ret *= facinv[a - b]; return ret; } mint multicomb(const ll a, const ll b) { return comb(a + b - 1, b); } template <typename T> struct Edge { int from, to; T cost; int id; Edge(int from_, int to_, T cost_, int id_) : from(from_), to(to_), cost(cost_), id(id_) {} Edge(int from_, int to_, T cost_) : from(from_), to(to_), cost(cost_) {} Edge(int from_, int to_) : from(from_), to(to_), cost(1) {} bool operator<(const Edge<T> &r) { return cost < r.cost; } }; template <typename T> ostream &operator<<(ostream &os, Edge<T> edge) { os << edge.from << " -> " << edge.to << " (" << edge.cost << ")"; return os; } // グラフテンプレート(隣接リスト) template <typename E = Edge<ll>> struct GraphL { // 頂点数、辺数 int n, m; // 隣接リスト vector<vector<E>> adj; GraphL(int n_) : n(n_), m(0), adj(n_) {} template <typename... Args> void add_edge(int from, int to, Args... args) { adj[from].emplace_back(from, to, args...); m++; } vector<E> &operator[](int i) { return adj[i]; } }; template <typename E = Edge<ll>> ostream &operator<<(ostream &os, GraphL<E> graph) { os << "V = " << graph.n << ", E = " << graph.m << "\n"; for (const auto &ev : graph.adj) { for (const auto &e : ev) { os << e << "\n"; } } return os; } struct UnionFind { // 木の頂点数と高さは根の値のみ意味がある vector<int> par, sizes, rank; int num_groups; UnionFind(int n) : par(n), sizes(n, 1), rank(n, 0), num_groups(n) { for (int i = 0; i < n; i++) par[i] = i; } int find(int x) { if (x == par[x]) return x; return par[x] = find(par[x]); // recursive, editing root } void unite(int x, int y) { x = find(x); y = find(y); if (x == y) return; if (rank[x] < rank[y]) swap(x, y); par[y] = x; sizes[x] += sizes[y]; if (rank[x] == rank[y]) rank[x]++; num_groups--; } bool same(int x, int y) { return find(x) == find(y); } int size(int x) { return sizes[find(x)]; } }; int main() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); ll n, m, x; cin >> n >> m >> x; GraphL<Edge<mint>> g(n); UnionFind uf(n); rep(i, m){ ll a, b, c; cin >> a >> b >> c; a--; b--; if(!uf.same(a, b)){ uf.unite(a, b); g.add_edge(a, b, mint(x).pow(c)); g.add_edge(b, a, mint(x).pow(c)); } } vector<bool> visited(n, false); mint ans = 0; vll v(n, 1); auto dfs = [&](auto& Self, int node) -> void{ visited[node] = true; for(auto&& e: g[node]){ if(!visited[e.to]){ Self(Self, e.to); v[node] += v[e.to]; ans += e.cost*v[e.to]*(n-v[e.to]); } } }; dfs(dfs, 0); dump(g); dump(v); print(ans); }