Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- struct DSU {
- vector<int> p;
- vector<int> d;
- DSU(int n) {
- p.resize(n);
- iota(p.begin(),p.end(),0);
- d.assign(n, 1);
- }
- int get(int v) {
- if(p[v] == v)
- return v;
- return p[v] = get(p[v]);
- }
- void uni(int a, int b) {
- a = get(a);
- b = get(b);
- if(a!=b) {
- if(d[a] < d[b]) {
- swap(a,b);
- }
- d[a] += d[b];
- p[b] = a;
- }
- }
- };
- vector<pair<int,int> > edges;
- map<pair<int,int>, int> mp;
- int main() {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- int n,m;
- cin>>n>>m;
- set<pair<int,int> > arr[11];
- for(int i=0; i<m; i++) {
- int f, t, w;
- cin>>f>>t>>w;
- f--,t--;
- edges.push_back({f, t});
- mp[{f,t}] = w;
- arr[w].insert({f,t});
- }
- vector<DSU> dsu(11, DSU(n));
- int q;
- cin>>q;
- int answer = 0;
- for(int i=0; i<=10; i++) {
- for(int j=0; j<=i; j++) {
- if(i == 10) {
- for(pair<int,int> p : arr[j]) {
- if(dsu[i].get(p.first) != dsu[i].get(p.second)) {
- answer += mp[p];
- dsu[i].uni(p.first, p.second);
- }
- }
- }
- for(pair<int,int> p : arr[j]) {
- dsu[i].uni(p.first, p.second);
- }
- }
- }
- while(q--) {
- int i;
- cin>>i;
- i--;
- pair<int,int> edge = edges[i];
- int nextW = mp[edge] - 1;
- mp[edge]--;
- if(dsu[nextW].get(edge.first) != dsu[nextW].get(edge.second)) {
- answer--;
- dsu[nextW].uni(edge.first, edge.second);
- }
- cout<<answer<<'\n';
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement