fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct DSU {
  5.     int n; vector<int> p, r;
  6.     DSU(int n=0): n(n), p(n), r(n,0){ iota(p.begin(), p.end(), 0); }
  7.     int find(int x){ return p[x]==x? x: p[x]=find(p[x]); }
  8.     bool unite(int a,int b){
  9.         a=find(a); b=find(b);
  10.         if(a==b) return false;
  11.         if(r[a]<r[b]) swap(a,b);
  12.         p[b]=a; if(r[a]==r[b]) r[a]++;
  13.         return true;
  14.     }
  15. };
  16.  
  17. struct Edge {int u,v; int w;};
  18.  
  19. const int LOG = 20; // enough for n<=1e5
  20.  
  21. int n, m, q;
  22. vector<vector<pair<int,int>>> g; // MST adjacency: to, w
  23. long long Wtot = 0;
  24.  
  25. int up[LOG][100005];
  26. int mx[LOG][100005];
  27. int depth_[100005];
  28. int tin[100005];
  29. int timer_ = 0;
  30.  
  31. void dfs(int u, int p, int w){
  32.     tin[u] = ++timer_;
  33.     up[0][u] = (p==-1? u : p);
  34.     mx[0][u] = (p==-1? 0 : w);
  35.     for (auto [v,c]: g[u]){
  36.         if (v==p) continue;
  37.         depth_[v] = depth_[u] + 1;
  38.         dfs(v,u,c);
  39.     }
  40. }
  41.  
  42. int maxOnPath(int u, int v){
  43.     if (u==v) return 0;
  44.     int res = 0;
  45.     if (depth_[u] < depth_[v]) swap(u,v);
  46.     int d = depth_[u] - depth_[v];
  47.     for (int k=LOG-1;k>=0;--k){
  48.         if (d>>k & 1){
  49.             res = max(res, mx[k][u]);
  50.             u = up[k][u];
  51.         }
  52.     }
  53.     if (u==v) return res;
  54.     for (int k=LOG-1;k>=0;--k){
  55.         if (up[k][u] != up[k][v]){
  56.             res = max(res, mx[k][u]);
  57.             res = max(res, mx[k][v]);
  58.             u = up[k][u];
  59.             v = up[k][v];
  60.         }
  61.     }
  62.     // now u and v are children of LCA
  63.     res = max(res, mx[0][u]);
  64.     res = max(res, mx[0][v]);
  65.     return res;
  66. }
  67.  
  68. struct Query{
  69.     int L, R, id, block;
  70. };
  71. int B; // block size for Mo
  72.  
  73. bool mo_cmp(const Query& a, const Query& b){
  74.     if (a.block != b.block) return a.block < b.block;
  75.     if (a.block & 1) return a.R > b.R;
  76.     return a.R < b.R;
  77. }
  78.  
  79. set<pair<int,int>> byTin; // (tin[v], v)
  80. vector<char> alive;
  81. long long curSum = 0;
  82.  
  83. int prevIndex(set<pair<int,int>>::iterator it){
  84.     if (it == byTin.begin()) return byTin.rbegin()->second;
  85.     return prev(it)->second;
  86. }
  87. int nextIndex(set<pair<int,int>>::iterator it){
  88.     ++it;
  89.     if (it == byTin.end()) return byTin.begin()->second;
  90.     return it->second;
  91. }
  92.  
  93. void addVertex(int v){
  94.     if (alive[v]) return;
  95.     alive[v] = 1;
  96.     if (byTin.empty()){
  97.         byTin.insert({tin[v], v});
  98.         return;
  99.     }
  100.     auto it = byTin.insert({tin[v], v}).first;
  101.     int a = prevIndex(it);
  102.     int b = nextIndex(it);
  103.     curSum -= maxOnPath(a,b);
  104.     curSum += maxOnPath(a,v) + maxOnPath(v,b);
  105. }
  106.  
  107. void removeVertex(int v){
  108.     if (!alive[v]) return;
  109.     alive[v] = 0;
  110.     if (byTin.size()==1){
  111.         byTin.clear();
  112.         curSum = 0;
  113.         return;
  114.     }
  115.     auto it = byTin.find({tin[v], v});
  116.     int a = prevIndex(it);
  117.     int b = nextIndex(it);
  118.     curSum -= maxOnPath(a,v) + maxOnPath(v,b);
  119.     curSum += maxOnPath(a,b);
  120.     byTin.erase(it);
  121. }
  122.  
  123. int main(){
  124.     ios::sync_with_stdio(false);
  125.     cin.tie(nullptr);
  126.  
  127.     if(!(cin>>n>>m>>q)) return 0;
  128.  
  129.     vector<Edge> edges(m);
  130.     for (int i=0;i<m;i++){
  131.         int u,v; long long w;
  132.         cin>>u>>v>>w;
  133.         edges[i]={u,v,(int)w};
  134.     }
  135.  
  136.     // 1) Build MST (assume the original graph is connected)
  137.     sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b){ return a.w < b.w; });
  138.     DSU dsu(n);
  139.     g.assign(n, {});
  140.     for (auto &e: edges){
  141.         if (dsu.unite(e.u, e.v)){
  142.             g[e.u].push_back({e.v, e.w});
  143.             g[e.v].push_back({e.u, e.w});
  144.             Wtot += e.w;
  145.         }
  146.     }
  147.  
  148.     // 2) LCA preprocess
  149.     depth_[0]=0;
  150.     dfs(0,-1,0);
  151.     for (int k=1;k<LOG;k++){
  152.         for (int v=0; v<n; v++){
  153.             up[k][v] = up[k-1][ up[k-1][v] ];
  154.             mx[k][v] = max(mx[k-1][v], mx[k-1][ up[k-1][v] ]);
  155.         }
  156.     }
  157.  
  158.     // 3) Read queries
  159.     vector<Query> qs(q);
  160.     B = max(1,(int)sqrt(n));
  161.     for (int i=0;i<q;i++){
  162.         int L,R; cin>>L>>R;
  163.         qs[i] = {L,R,i, L/B};
  164.     }
  165.     sort(qs.begin(), qs.end(), mo_cmp);
  166.  
  167.     // 4) Mo's algorithm over [L,R] on vertex IDs
  168.     vector<long long> ans(q);
  169.     alive.assign(n, 0);
  170.     int curL = 0, curR = -1;
  171.     for (auto &qq: qs){
  172.         int L = qq.L, R = qq.R;
  173.         while (curL > L) addVertex(--curL);
  174.         while (curR < R) addVertex(++curR);
  175.         while (curL < L) removeVertex(curL++);
  176.         while (curR > R) removeVertex(curR--);
  177.         ans[qq.id] = Wtot - (curSum/2);
  178.     }
  179.  
  180.     for (int i=0;i<q;i++){
  181.         cout << ans[i] << '\n';
  182.     }
  183.     return 0;
  184. }
  185.  
Success #stdin #stdout 0.01s 18056KB
comments (?)
stdin 
5 5 3
0 1 2
0 2 5
0 3 6
1 2 3
2 4 3
1 1
1 4
3 4
stdout 
14
5
8
https://ideone.com/Nbr4n6
language:
C++14 (gcc 8.3)
created:
15 days 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!