結果

問題 No.1207 グラフX
ユーザー risujiroh
提出日時 2020-08-30 13:14:53
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 296 ms / 2,000 ms
コード長 4,042 bytes
コンパイル時間 4,030 ms
コンパイル使用メモリ 259,696 KB
最終ジャッジ日時 2025-01-13 20:58:07
ジャッジサーバーID
(参考情報)
judge3 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 46
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/extc++.h>
#ifndef DUMP
#define DUMP(...) void(0)
#endif
using namespace std;
template <class T, class Op = multiplies<>>
constexpr T power(T a, uint64_t n, T init = 1, Op op = Op{}) {
while (n) {
if (n & 1) init = op(init, a);
if (n >>= 1) a = op(a, a);
}
return init;
}
template <uint32_t Mod>
struct modular {
using T = modular;
static constexpr uint32_t mod = Mod;
uint32_t v;
modular(int64_t x = 0) : v((x %= mod) < 0 ? x + mod : x) {}
T operator-() const { return T() - *this; }
T& operator+=(T b) { return v += int(v += b.v - mod) < 0 ? mod : 0, *this; }
T& operator-=(T b) { return v += int(v -= b.v) < 0 ? mod : 0, *this; }
T& operator*=(T b) { return v = uint64_t(v) * b.v % mod, *this; }
T& operator/=(T b) { return *this *= power(b, mod - 2); }
friend T operator+(T a, T b) { return a += b; }
friend T operator-(T a, T b) { return a -= b; }
friend T operator*(T a, T b) { return a *= b; }
friend T operator/(T a, T b) { return a /= b; }
friend bool operator==(T a, T b) { return a.v == b.v; }
};
struct dsu {
int cc;
vector<int> p, sz;
dsu(int n = 0) : cc(n), p(n, -1), sz(n, 1) {}
int root(int v) {
if (p[v] == -1) return v;
return p[v] = root(p[v]);
}
bool unite(int u, int v) {
u = root(u), v = root(v);
if (u == v) return false;
--cc;
if (sz[u] < sz[v]) swap(u, v);
p[v] = u;
sz[u] += sz[v];
return true;
}
bool same(int u, int v) { return root(u) == root(v); }
int size(int v) { return sz[root(v)]; }
};
struct graph {
struct edge {
int src, dst, cost;
int operator-(int v) const { return src ^ dst ^ v; }
};
int n, m;
vector<edge> edges;
vector<vector<pair<int, int>>> adj;
graph(int _n = 0) : n(_n), m(0), adj(n) {}
int add(const edge& e, bool directed = false) {
edges.push_back(e);
adj[e.src].emplace_back(m, e.dst);
if (not directed) adj[e.dst].emplace_back(m, e.src);
return m++;
}
};
struct dfs_forest : graph {
using T = decltype(edge::cost);
vector<int> root, pv, pe, sz, dep, min_dep, last, ord, in, out;
vector<T> dist;
int trials;
dfs_forest(int _n = 0) : graph(_n), dist(n), trials(0) {
for (auto p : {&root, &pv, &pe, &sz, &dep, &min_dep, &last, &in, &out})
p->assign(n, -1);
}
int add(const edge& e) { return graph::add(e); }
void dfs(int v) {
sz[v] = 1, min_dep[v] = dep[v], last[v] = trials;
in[v] = size(ord), ord.push_back(v);
for (auto [id, u] : adj[v]) {
if (id == pe[v]) continue;
if (last[u] == trials) {
min_dep[v] = min(min_dep[v], dep[u]);
continue;
}
root[u] = root[v], pv[u] = v, pe[u] = id, dep[u] = dep[v] + 1;
dist[u] = dist[v] + edges[id].cost;
dfs(u);
sz[v] += sz[u], min_dep[v] = min(min_dep[v], min_dep[u]);
}
out[v] = size(ord);
}
void build(int r, bool clear_ord = true) {
root[r] = r, pv[r] = pe[r] = -1, dep[r] = 0, dist[r] = T{};
if (clear_ord) ord.clear();
dfs(r);
++trials;
}
void build() {
fill(begin(root), end(root), -1);
for (int v = 0; v < n; ++v)
if (root[v] == -1) build(v, v == 0);
}
int farther(int id) const {
int u = edges[id].src, v = edges[id].dst;
return dep[u] < dep[v] ? v : u;
}
bool spans(int id) const { return id == pe[farther(id)]; }
bool anc(int u, int v) const { return in[u] <= in[v] and out[v] <= out[u]; }
};
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n, m, base;
cin >> n >> m >> base;
dsu d(n);
dfs_forest g(n);
while (m--) {
int u, v, z;
cin >> u >> v >> z;
--u, --v;
if (d.same(u, v)) continue;
d.unite(u, v);
g.add({u, v, z});
}
g.build();
using mint = modular<power(10, 9) + 7>;
mint res;
for (int v = 1; v < n; ++v) {
res += power<mint>(base, g.edges[g.pe[v]].cost) * g.sz[v] * (n - g.sz[v]);
}
cout << res.v << '\n';
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0