Submission #1178047

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178047		akamizane	Bridges (APIO19_bridges)	C++20	100 / 100	1538 ms	172288 KiB

bridges

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


#define debug(...) 42


const int maxn = 1e5 + 1;
const int block = 1000;

int sz[maxn], par[maxn], n, m, q;
stack<pair<int&,int>> stk;

void reset(){
  iota(par + 1, par + n + 1, 1);
  fill(sz + 1, sz + n + 1, 1);
}

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

void merge(int a, int b){
  a = find(a);
  b = find(b);
  if (a == b) return;
  if (sz[a] < sz[b]) swap(a, b);
  stk.push({sz[a], sz[a]});
  stk.push({par[b], par[b]});
  sz[a] += sz[b];
  par[b] = a;
}

void rollback(int x){
  while(stk.size() > x){
    auto [a, b] = stk.top();
    a = b;
    stk.pop();
  }
}

int u[maxn], v[maxn], w[maxn], t[maxn], x[maxn], y[maxn];
bool changed[maxn];
vector<int> join[block];
int ans[maxn]; 

void solve(){
    cin >> n >> m;
    for (int i = 1; i <= m; i++) cin >> u[i] >> v[i] >> w[i];
    cin >> q;
    debug(n, m, q);
    for (int i = 1; i <= q; i++) cin >> t[i] >> x[i] >> y[i];
    for (int l = 1; l <= q; l += block){
      int r = min(q + 1, l + block);
      reset();
      fill(changed + 1, changed + m + 1, false);
      vector<int> ask, up, unchanged;
      for (int i = l; i < r; i++){
        if (t[i] == 1){
          changed[x[i]] = true;
          up.push_back(i);
        }
        else ask.push_back(i);
      }
      for (int i = 1; i <= m; i++) if (!changed[i]) unchanged.push_back(i);
      for (int i = l; i < r; i++){
        if (t[i] == 1){
          w[x[i]] = y[i];
        }
        else{
          join[i - l].clear();
          for (auto j : up) {
            if (w[x[j]] >= y[i]) join[i - l].push_back(x[j]);
          }
        }
      }
      sort(ask.begin(), ask.end(), [&] (int i, int j){
        return y[i] > y[j];
      });
      sort(unchanged.begin(), unchanged.end(), [&] (int i, int j){
        return w[i] > w[j];
      });
      int it = 0;
      for (auto i : ask){
        while(it < unchanged.size() && w[unchanged[it]] >= y[i]){
          merge(u[unchanged[it]], v[unchanged[it]]);
          it++;
        }
        int prev = stk.size();
        for (auto j : join[i - l]) merge(u[j], v[j]);
        ans[i] = sz[find(x[i])];
        rollback(prev);
      }
    }
    for (int i = 1; i <= q; i++) if (t[i] == 2) cout << ans[i] << "\n";
}

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int tt = 1;
  // cin >> tt;
  while (tt--){
    solve();
  }
  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