fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std ;
  4.  
  5. #define ll long long
  6. #define sz(x) x.size()
  7. // bitmasks
  8. // Number of leading zeroes: __builtin_clz(x)
  9. // Number of trailing zeroes : __builtin_ctz(x)
  10. // Number of 1-bits: __builtin_popcount(x);
  11. // last one : __lg()
  12. template<typename T = ll, ll Base = 1>
  13. struct DSU {
  14.     vector<T> parent, Gsize, nxt, tail, pos, roots;
  15.  
  16.     DSU(ll MaxNodes) {
  17.         parent = Gsize = roots = tail = pos = nxt = vector<T>(MaxNodes + Base);
  18.         for (ll i = Base; i < MaxNodes + Base; i++) {
  19.             parent[i] = roots[i] = pos[i] = tail[i] = i;
  20.             nxt[i] = -1, Gsize[i] = 1;
  21.         }
  22.     }
  23.  
  24.     T find_leader(ll node) {
  25.         return parent[node] = (parent[node] == node ? node : find_leader(parent[node]));
  26.     }
  27.  
  28.     bool is_same_sets(ll u, ll v) {
  29.         return find_leader(u) == find_leader(v);
  30.     }
  31.  
  32.     bool union_sets(ll u, ll v) {
  33.         ll leader_u = find_leader(u), leader_v = find_leader(v);
  34.         if (leader_u == leader_v) return 0;
  35.         // make leader_u is the leader with the larger component
  36.         if (Gsize[leader_u] < Gsize[leader_v])
  37.             swap(leader_u, leader_v);
  38.         ll p = pos[leader_v];
  39.         Gsize[leader_u] += Gsize[leader_v];
  40.         parent[leader_v] = leader_u;
  41.         roots[p] = roots.back();
  42.         pos[roots[p]] = p;
  43.         roots.pop_back();
  44.         nxt[tail[leader_u]] = leader_v;
  45.         tail[leader_u] = tail[leader_v];
  46.         return 1;
  47.     }
  48.  
  49.     void print() {
  50.         for (ll root = Base; root < sz(roots); root++) {
  51.             for (ll u = roots[root]; ~u; u = nxt[u])
  52.                 cout << u << " \n"[!~nxt[u]];
  53.         }
  54.     }
  55.  
  56.     vector<vector<ll> > get_components() {
  57.         vector<vector<ll> > components;
  58.         for (ll root = Base; root < sz(roots); root++) {
  59.             vector<ll> component;
  60.             for (ll u = roots[root]; ~u; u = nxt[u])
  61.                 component.push_back(u);
  62.             components.push_back(component);
  63.         }
  64.         return components;
  65.     }
  66.  
  67.     ll get_size(ll u) {
  68.         return Gsize[find_leader(u)];
  69.     }
  70.  
  71.     ll get_components_number() {
  72.         return sz(roots) - Base;
  73.     }
  74.  
  75.     ll has_supervisor(ll b) {
  76.         return parent[b] != b;
  77.     }
  78. };
  79.  
  80. struct edge {
  81.     ll u, v, w;
  82. };
  83.  
  84. const ll MOD = 1e9;
  85.  
  86. void solve() {
  87.     ll n;
  88.     cin >> n;
  89.     ll m;
  90.     cin >> m;
  91.     vector<edge> E(m);
  92.     for (ll i = 0; i < m; i++) {
  93.         cin >> E[i].u >> E[i].v >> E[i].w;
  94.     }
  95.  
  96.     sort(E.begin(), E.end(), [&](const edge &x, const edge &y) {
  97.         return x.w > y.w;
  98.     });
  99.  
  100.     ll ans = 0, current_pairs = 0;
  101.     DSU<ll> dsu(n);
  102.     for (auto &e: E) {
  103.         ll u = e.u, v = e.v, w = e.w;
  104.         ll up = dsu.find_leader(u), vp = dsu.find_leader(v);
  105.         ll us = dsu.get_size(u), vs = dsu.get_size(v);
  106.         ll num = current_pairs;
  107.         if (up != vp) {
  108.             num += us * vs;
  109.         }
  110.         ans = (ans + w * (num % MOD) % MOD) % MOD;
  111.         if (up != vp) {
  112.             dsu.union_sets(u, v);
  113.             current_pairs += us * vs;
  114.         }
  115.     }
  116.  
  117.     cout << ans << endl;
  118. }
  119.  
  120. int main() {
  121.     ios::sync_with_stdio(false);
  122.     cin.tie(nullptr);
  123.     // ll t;
  124.     // cin >> t;
  125.     // while (t--)
  126.     solve();
  127. }
  128.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/d30qEP
each weight contribute to all the pair of nodes created in its moment all the pairs that are already created
language:
C++14 (gcc 8.3)
created:
15 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!