Submission #1191543

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191543		epicci23	Bridges (APIO19_bridges)	C++20	59 / 100	3096 ms	12588 KiB

bridges

#include "bits/stdc++.h"
#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;

const int N = 1e5 + 5;
const int BL = 400;

int ans[N];

struct DSU{
  stack<array<int,3>> st;
  vector<int> siz,par;
  DSU(int _n){
    siz.assign(_n + 5, 1);
    par.resize(_n + 5);
    iota(all(par),0);
  }

  int find(int a){
    if(a==par[a]) return a;
    return find(par[a]);
  }

  void unite(int a,int b){
    a=find(a),b=find(b);
    if(a==b){
      st.push({-1, -1, -1});
      return;
    }
    if(siz[a] > siz[b]) swap(a, b);
    st.push({a, b, siz[a]});
    par[a] = b;
    siz[b] += siz[a];
  }

  void rollback(){
    auto [a, b, w] = st.top();
    st.pop();
    if(a == -1) return;
    par[a] = a;
    siz[b] -= w;
  }
};


void _(){

  memset(ans,-1,sizeof(ans));

	int n, m;
  cin >> n >> m;
  
  vector<array<int,3>> v;
  for(int i=0;i<m;i++){
    int a,b,c;
    cin >> a >> b >> c;
    v.push_back({a,b,c});
  }
  reverse(all(v));
  v.push_back({-1, -1, -1});
  reverse(all(v));

  int q;
  cin >> q;

  vector<array<int,3>> Ops;

  for(int i=0;i<q;i++){
    int op;
    cin >> op;
    if(op == 1){
      int ind, val;
      cin >> ind >> val;
      Ops.push_back({op, ind, val});
    }
    else{
      int node, val;
      cin >> node >> val;
      Ops.push_back({op, node, val});
    }
  }

  for(int i = 0; i < q; i += BL){
    // [i, i + BL - 1]
    bitset<N> mark;
    vector<array<int,3>> edg;
    vector<int> Change(m + 2, -1), Ind;
    stack<array<int,2>> st;
    
    for(int j = 1; j <= m; j++) Change[j] = v[j][2];
    for(int j = i; j < min(q, i + BL); j++) if(Ops[j][0] == 1) mark[Ops[j][1]] = 1;
    
    for(int j = 1; j <= m; j++){
      if(mark[j]) Ind.push_back(j);
      else edg.push_back({v[j][2], v[j][0], v[j][1]});
    }

    sort(all(edg));
    reverse(all(edg));
    vector<array<int,2>> Queries;

    for(int j = i; j < min(q, i + BL); j++) if(Ops[j][0] == 2) Queries.push_back({Ops[j][2], j});

    sort(all(Queries));
    reverse(all(Queries));
    DSU dsu(n + 5);
    
    int ptr = 0;

    for(auto [w, ind] : Queries){
      
      //cout << " w : " << w << " ind : " << ind << '\n';

      for(int j = i; j <= ind; j++){ 
       if(Ops[j][0] == 1){
        st.push({Ops[j][1], Change[Ops[j][1]]});
        Change[Ops[j][1]] = Ops[j][2];
       }
      }
      
      while(ptr < sz(edg) && edg[ptr][0] >= w){
        //cout << "birles : " << edg[ptr][1] << ' ' << edg[ptr][2] << '\n';
        dsu.unite(edg[ptr][1], edg[ptr][2]);
        ptr++;
      }
      
      int geri = 0;

      for(int u : Ind){
        //cout << "degisen : " << u << '\n';
        //cout << Change[u] << '\n';
        if(Change[u] >= w){
          dsu.unite(v[u][0], v[u][1]);
          geri++;
        }
      }

      ans[ind] = dsu.siz[dsu.find(Ops[ind][1])];

      while(!st.empty()){
        Change[st.top()[0]] = st.top()[1];
        st.pop();
      }
      while(geri--) dsu.rollback();
    }

    for(int j = i; j < min(q, i + BL); j++) if(Ops[j][0] == 1) v[Ops[j][1]][2] = Ops[j][2];
  }


  for(int i = 0; i < N; i++){
    if(ans[i] == -1) continue;
    cout << ans[i] << '\n';
  }
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}

• Subtask 1: 13 / 13
• Subtask 2: 16 / 16
• Subtask 3: 17 / 17
• Subtask 4: 0 / 14
• Subtask 5: 13 / 13
• Subtask 6: 0 / 27