Submission #924015

#	Time	Username	Problem	Language	Result	Execution time	Memory
924015		Arp	Bridges (APIO19_bridges)	C++17	100 / 100	1615 ms	30360 KiB

bridges

#include<bits/stdc++.h>
using namespace std;

const int B = 1000;
const int M = 1e5;

int sz[M + 1];
int par[M + 1];
stack<int> st;

void init(){
  for(int i = 1; i <= M;i++){
    sz[i] = 1;
    par[i] = i;
  }
}

int find(int a){
  // if(par[a] == a){
  //   return a;
  // }
  // return par[a] = find(par[a]);
  while(a != par[a]) a = par[a];
  return a;
}
void join(int a,int b){
  a = find(a);
  b = find(b);
  if(a == b) return;
  if(sz[a] > sz[b]) swap(a,b);
  sz[b] += sz[a];
  par[a] = par[b];
  st.push(a);
}

void rollback(int s){
  while((int) st.size() > s){
    int a = st.top();
    st.pop();
    sz[par[a]] -= sz[a];
    par[a] = a; 
  }
}

int main(){

  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n,m;
  cin >> n >> m;
  vector<array<int,3>> bridge(m + 1);
  for(int i = 1;i <= m;i++){
    cin >> bridge[i][0] >> bridge[i][1] >> bridge[i][2];
  }
  int q;
  cin >> q;
  vector<array<int,3>> query(q);
  for(int i = 0;i < q;i++){
    cin >> query[i][0] >> query[i][1] >> query[i][2];
  }
  vector<int> ans(q);
  for(int i = 0;i < q;i += B){
    init();
    int l = i;
    int r = min(q - 1,i + B);
    vector<bool> isc(m + 1,false);
    vector<int> upd,ask;
    vector<vector<int>> tj(r - l + 1);
    for(int j = l;j <= r;j ++){
      if(query[j][0] == 1) upd.push_back(query[j][1]);
    }
    for(int j = l;j <= r;j ++){
      if(query[j][0] == 1){
        isc[query[j][1]] = true;
        bridge[query[j][1]][2] = query[j][2];
      }else{
      for(int k : upd){
        if(bridge[k][2] >= query[j][2]) tj[j - l].push_back(k);
      }
      ask.push_back(j);
      }
    }
    vector<int> uc;
    for(int j = 1;j <= m;j++){
      if(!isc[j]){
        uc.push_back(j);
      }
    }
    sort(uc.begin(),uc.end(),[&](int &a,int &b){
      return bridge[a][2] > bridge[b][2];
    });
    sort(ask.begin(),ask.end(),[&](int &a,int &b){
      return query[a][2] > query[b][2];
    });
    int cur = 0;
    for(int k : ask){
      int w = query[k][2];
      while(cur < (int) uc.size() && bridge[uc[cur]][2] >= w){
        join(bridge[uc[cur]][0],bridge[uc[cur]][1]);
         ++ cur;
      }
      int ps = st.size();
      for(int e : tj[k - l]){
        join(bridge[e][0],bridge[e][1]);
      }
      int my = query[k][1];
      ans[k] = sz[find(my)];
      rollback(ps);
    }
  }
  for(int i = 0;i < q;i++){
    if(query[i][0] == 2) cout << ans[i] << '\n';
  }
  return 0;
}

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