Advertisement
999ms

Untitled

May 26th, 2019
188
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.57 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. struct DSU {
  4.   vector<int> p;
  5.   vector<int> d;
  6.   DSU(int n) {
  7.     p.resize(n);
  8.     iota(p.begin(),p.end(),0);
  9.     d.assign(n, 1);
  10.   }
  11.   int get(int v) {
  12.     if(p[v] == v)
  13.       return v;
  14.     return p[v] = get(p[v]);
  15.   }
  16.   void uni(int a, int b) {
  17.     a = get(a);
  18.     b = get(b);
  19.     if(a!=b) {
  20.       if(d[a] < d[b]) {
  21.         swap(a,b);
  22.       }
  23.       d[a] += d[b];
  24.       p[b] = a;
  25.     }
  26.   }
  27. };
  28.  
  29. vector<pair<int,int> > edges;
  30. map<pair<int,int>, int> mp;
  31.  
  32. int main() {
  33.   ios_base::sync_with_stdio(false);
  34.   cin.tie(nullptr);
  35.   int n,m;
  36.   cin>>n>>m;
  37.   set<pair<int,int> > arr[11];
  38.   for(int i=0; i<m; i++) {
  39.     int f, t, w;
  40.     cin>>f>>t>>w;
  41.     f--,t--;
  42.     edges.push_back({f, t});
  43.     mp[{f,t}] = w;
  44.     arr[w].insert({f,t});
  45.   }
  46.   vector<DSU> dsu(11, DSU(n));
  47.   int q;
  48.   cin>>q;
  49.   int answer = 0;
  50.   for(int i=0; i<=10; i++) {
  51.     for(int j=0; j<=i; j++) {
  52.       if(i == 10) {
  53.         for(pair<int,int> p : arr[j]) {
  54.           if(dsu[i].get(p.first) != dsu[i].get(p.second)) {
  55.             answer += mp[p];
  56.             dsu[i].uni(p.first, p.second);
  57.           }
  58.         }
  59.       }
  60.       for(pair<int,int> p : arr[j]) {
  61.         dsu[i].uni(p.first, p.second);
  62.       }
  63.     }
  64.   }
  65.  
  66.  
  67.   while(q--) {
  68.     int i;
  69.     cin>>i;
  70.     i--;
  71.     pair<int,int> edge = edges[i];
  72.     int nextW = mp[edge] - 1;
  73.     mp[edge]--;
  74.     if(dsu[nextW].get(edge.first) != dsu[nextW].get(edge.second)) {
  75.             answer--;
  76.             dsu[nextW].uni(edge.first, edge.second);
  77.     }
  78.     cout<<answer<<'\n';
  79.   }
  80.  
  81.   return 0;
  82. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement