fork download
copy 
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3. #define all(x) begin(x),end(x)
  4. typedef long long ll;
  5. typedef vector<int> vi;
  6.  
  7. const int oo = 1e9;
  8.  
  9. struct DSU{
  10.     vector<int> sz,parent;
  11.     int components;
  12.     void reset(int n) {
  13.         fill(sz.begin(),sz.begin()+n,1);
  14.         iota(parent.begin(),parent.begin()+n,0);
  15.         components=n;
  16.     }
  17.     DSU(int n) : sz(n),parent(n) {
  18.         reset(n);
  19.     }
  20.     void link(int a, int b) {
  21.         components--;
  22.         if(sz[a]<sz[b]) swap(a,b);
  23.         sz[a]+=sz[b];
  24.         parent[b] = a;
  25.     }
  26.     bool unite(int a, int b) {
  27.         int pa = find(a), pb = find(b);
  28.         if(pa!=pb) {
  29.             link(pa,pb);
  30.             return true;
  31.         }
  32.         return false;
  33.     }
  34.     int find(int a) {
  35.         if(a==parent[a]) return a;
  36.         return parent[a] = find(parent[a]);
  37.     }
  38. };
  39.  
  40. struct dynamicMST {
  41.     struct edge {
  42.         int l,r;
  43.         int u,v,w;
  44.         bool operator<(const edge& o) {
  45.             return w<o.w;
  46.         }
  47.     };
  48.     vector<edge> ives; // edges + time interval that they are active.
  49.     vector<array<int,3>> startes; 
  50.     vi touch; // last time this edge was touched
  51.     int totaln;
  52.     DSU dsu,dsu2;
  53.     vi id;
  54.     dynamicMST(vector<array<int,3>> ES, int n) : startes(ES), touch(ES.size()), totaln(n), dsu(n),dsu2(n), id(n)  {
  55.         // give all edges upfront.
  56.     }
  57.     int q=0;
  58.     void update(int i, int x) {
  59.         // update edge weight of edge i to x
  60.         // if you want to delete the edge, just set it to infinity
  61.         q++;
  62.         auto& [u,v,w] = startes[i];
  63.         ives.push_back({touch[i],q,u,v,w});
  64.         touch[i]=q;
  65.         w = x;
  66.     }
  67.     vector<ll> ans;
  68.     void solve(int l, int r, vector<edge> es, int n, ll cost=0) {
  69.         // remove edges that don't belong to this interval
  70.         es.erase(stable_partition(all(es),[&](const edge& e) {return !(e.r<=l or r<=e.l);}),es.end());
  71.         dsu.reset(n),dsu2.reset(n);
  72.  
  73.         // compressing connected components
  74.         for(auto& e : es) if(l<e.l or e.r<r) { // active edges
  75.             dsu.unite(e.u,e.v);
  76.         }
  77.  
  78.         for(auto& e : es) if(e.l<=l and r<=e.r) { // fully overlapping edges
  79.             if(dsu.unite(e.u,e.v)) {
  80.                 cost+=e.w;
  81.                 dsu2.unite(e.u,e.v);
  82.             }
  83.         }
  84.  
  85.         if(l+1==r) { // base case, we found the MST.
  86.             ans[l]=cost;
  87.             return;
  88.         }
  89.  
  90.         int cnt=0; // relabel all connected components to 0...cnt-1
  91.         for(int i=0;i<n;++i) if(dsu2.find(i)==i) id[i]=cnt++;
  92.         dsu.reset(cnt);
  93.         for(auto& e : es) { // relabeling and marking useless edges
  94.             e.u = id[dsu2.find(e.u)], e.v = id[dsu2.find(e.v)];
  95.             if(e.l<=l and r<=e.r) {
  96.                 if(!dsu.unite(e.u,e.v)) e.l=oo,e.r=-oo; // mark useless edge, will get deleted in next step
  97.             }
  98.         }
  99.         int m = (l+r)/2;
  100.         solve(l,m,es,cnt,cost);
  101.         solve(m,r,es,cnt,cost);
  102.     }
  103.     vector<ll> run() {
  104.         int m = startes.size();
  105.         q++;
  106.         for(int i=0;i<m;++i) {
  107.             auto& [u,v,w] = startes[i];
  108.             ives.push_back({touch[i],q,u,v,w});
  109.         }
  110.  
  111.         sort(all(ives)); // (q+m) log(q+m) time
  112.         ans.resize(q);
  113.         solve(0,q,ives,totaln); // (q+m) log(q) alpha(n) time
  114.         return ans;
  115.     }
  116. };
  117.  
  118. int main() {
  119.     ios_base::sync_with_stdio(false);
  120.     cin.tie(NULL);
  121.     int n,m,q; cin >> n >> m >> q;
  122.     vector<array<int,3>> es(m);
  123.  
  124.     for(auto& [u,v,w] : es) {
  125.         cin >> u >> v >> w;
  126.         --u,--v;
  127.     }
  128.  
  129.     dynamicMST mst(es,n);
  130.  
  131.     for(int i=0;i<q;++i) {
  132.         int k,d;
  133.         cin >> k >> d, --k;
  134.         mst.update(k,d);
  135.     }
  136.     auto ans = mst.run();
  137.     for(int i=1;i<=q;++i) { // ans[0] gives the MST cost of the initial MST.
  138.         cout << ans[i] << '\n';
  139.     }
  140.  
  141. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/kYq4XU
language:
C++14 (gcc 8.3)
created:
11 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!