제출 #1327935

#제출 시각아이디문제언어결과실행 시간메모리
1327935DeltaStruct다리 (APIO19_bridges)C++20
100 / 100
2291 ms12636 KiB
#include <bits/stdc++.h>
using namespace std;

int root(vector<int>& UF,int x){
  if (UF[x]==-1) return x;
  return UF[x] = root(UF,UF[x]);
}

int main(){
  ios::sync_with_stdio(false),cin.tie(0);
  int n,m; cin >> n >> m; vector<tuple<int,int,int>> A(m);
  for (auto& [c,a,b]:A) (cin>>a>>b>>c),--a,--b;
  multiset<tuple<int,int,int>,greater<tuple<int,int,int>>> E(A.begin(),A.end());
  int q; cin >> q; vector<int> T(q),B(q),C(q);
  for (int i(0);i < q;++i) (cin>>T[i]>>B[i]>>C[i]),--B[i];
  int s = sqrt(q);
  vector<int> D(m,-1),R(q),UF(n,-1),SZ(n,1),vis(n,1); vector<vector<int>> G(n);
  for (int i(0);i < q;i+=s){
    int e = min(i+s,q);
    vector<int> F;
    priority_queue<pair<int,int>> Q;
    for (int k(i);k < e;++k) if (T[k]==1){
      if (D[B[k]]==-1) E.erase(E.find(A[B[k]])),F.emplace_back(B[k]);
      D[B[k]] = k;
    } else {
      Q.emplace(C[k],k);
    }
    sort(F.begin(),F.end()),F.erase(unique(F.begin(),F.end()),F.end());
    int f = F.size();
    vector<int> H(f),I(s);
    for (int i(0);i < f;++i) H[i] = get<0>(A[F[i]]);
    vector HB = H;
    for (int k(i);k < e;++k) if (T[k]==1) I[k-i] = lower_bound(F.begin(),F.end(),B[k])-F.begin();
    fill(UF.begin(),UF.end(),-1),fill(SZ.begin(),SZ.end(),1);
    auto solve = [&]() -> void {
      auto [x,y] = Q.top(); Q.pop();
      for (int k(i);k < y;++k) if (T[k]==1) H[I[k-i]] = C[k];
      for (int k(0);k < f;++k) if (H[k]>=x){
        G[root(UF,get<1>(A[F[k]]))].emplace_back(root(UF,get<2>(A[F[k]])));
        G[root(UF,get<2>(A[F[k]]))].emplace_back(root(UF,get<1>(A[F[k]])));
      }
      queue<int> que; que.emplace(root(UF,B[y])),vis[root(UF,B[y])] = 0;
      while(!que.empty()){
        int a = que.front(); que.pop();
        R[y] += SZ[a];
        for (int b:G[a]) if (vis[b]) vis[b] = 0,que.emplace(b);
      }
      vis[root(UF,B[y])] = 1;
      for (int k(0);k < f;++k) if (H[k]>=x){
        G[root(UF,get<1>(A[F[k]]))].clear(),vis[root(UF,get<1>(A[F[k]]))] = 1;
        G[root(UF,get<2>(A[F[k]]))].clear(),vis[root(UF,get<2>(A[F[k]]))] = 1;
      }
      H = HB;
    };
    for (auto [c,a,b]:E){
      if (Q.empty()) break;
      while(!Q.empty()&&Q.top().first>c) solve();
      int x = root(UF,a),y = root(UF,b);
      if (SZ[x]>SZ[y]) swap(x,y);
      if (x==y) continue;
      UF[x] = y,SZ[y] += SZ[x];
    }
    while(!Q.empty()) solve();
    for (int k(i);k < e;++k) if (T[k]==1) get<0>(A[B[k]]) = C[k],D[B[k]] = -1;
    for (int k:F) E.emplace(A[k]);
  }
  for (int i(0);i < q;++i) if (T[i]==2) cout << R[i] << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...