Submission #930752

#	Time	Username	Problem	Language	Result	Execution time	Memory
930752		rxlfd314	Bridges (APIO19_bridges)	C++17	100 / 100	1472 ms	7428 KiB

bridges

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
 
#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)
 
#define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d))
#define FOR(a, b, c) REP(a, b, c, 1)
#define ROF(a, b, c) REP(a, b, c, -1)
 
signed main() {
#ifndef DEBUG
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
#endif
  int N, M;
  cin >> N >> M;
  int A[M], B[M], D[M];
  FOR(i, 0, M-1)
    cin >> A[i] >> B[i] >> D[i], A[i]--, B[i]--;
  
  constexpr int BSZ = 1050;
  int Q;
  cin >> Q;
  int ans[Q];
  memset(ans, -1, sizeof(ans));
  REP(q, 0, Q-1, BSZ) {
    vt<ari3> qrys, upds;
    bool bad[M] = {};
    int edge_cnt = M;
    FOR(i, q, min(Q, q+BSZ)-1) {
      int qt, a, b;
      cin >> qt >> a >> b;
      if (qt == 1)
        upds.push_back({i, --a, b}), edge_cnt -= !bad[a], bad[a] = true;
      else
        qrys.push_back({b, --a, i});
    }
    sort(all(qrys), greater<ari3>());
    reverse(all(upds));
    const int upd_size = size(upds);
    int edges[edge_cnt], edge_ptr = 0;
    FOR(i, 0, M-1) {
      if (bad[i])
        upds.push_back({-1, i, D[i]});
      else
        edges[edge_ptr++] = i;
    }
    sort(edges, edges + edge_cnt, [&](const int &a, const int &b) {
      return D[a] < D[b];
    });
    
    int uf[N], op_ptr = 0;
    ari2 ops[N];
    memset(uf, -1, sizeof(uf));
    function<int(int)> find2 = [&](int i) {
      return uf[i] < 0 ? i : uf[i] = find2(uf[i]);
    };
    auto find = [&](int i, bool b) {
      if (!b)
        return find2(i);
      while (uf[i] >= 0)
        i = uf[i];
      return i;
    };
    auto unite = [&](int a, int b, bool c) {
      if ((a = find(a, c)) == (b = find(b, c)))
        return false;
      if (uf[a] > uf[b])
        swap(a, b);
      if (c)
        ops[op_ptr++] = {b, uf[b]};
      uf[a] += uf[b];
      uf[b] = a;
      return true;
    };
    auto rollback = [&]() {
      auto [b, v] = ops[--op_ptr];
      uf[uf[b]] -= v;
      uf[b] = v;
    };
 
    bool seen[M] = {};
    for (auto [w, i, qi] : qrys) {
      while (edge_ptr && D[edges[edge_ptr-1]] >= w) {
        edge_ptr--;
        unite(A[edges[edge_ptr]], B[edges[edge_ptr]], 0);
      }
      int cnt = 0;
      for (auto [ui, b, k] : upds) {
        if (ui > qi)
          continue;
        if (!seen[b] && k >= w)
          cnt += unite(A[b], B[b], 1);
        seen[b] = true;
      }
      ans[qi] = -uf[find(i, 1)];
      while (cnt--)
        rollback();
      FOR(j, upd_size, size(upds)-1)
        seen[upds[j][1]] = false;
    }
 
    FOR(i, 0, upd_size-1) { // cOnStAnT oPtImIsAtIoN
      auto [ui, b, k] = upds[i];
      if (seen[b])
        continue;
      D[b] = k;
      seen[b] = true;
    }
  }
 
  FOR(i, 0, Q-1)
    if (~ans[i])
      cout << ans[i] << '\n';
}

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