Submission #538451

#	Time	Username	Problem	Language	Result	Execution time	Memory
538451		schiftyfive4	Bridges (APIO19_bridges)	C++17	100 / 100	2288 ms	9576 KiB

bridges

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

#ifdef LOCAL
#include "debug.hpp"
#else
#define debug(...) "MJ >> LAMELO"
#endif

const int B = 800;

struct DSU {
  vector<int> f, siz, st;
  DSU(int n) : f(n), siz(n, 1) {
    iota(f.begin(), f.end(), 0);
  }
  int find(int x) {
    while (x != f[x]) {
      // x = f[x] = f[f[x]];
      x = f[x];
    }
    return x;
  }
  bool same(int x, int y) {
    return find(x) == find(y);
  }
  bool merge(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) {
      return false;
    }
    if (siz[y] > siz[x]) {
      swap(x, y);
    }
    siz[x] += siz[y];
    f[y] = x;
    st.push_back(y);
    return true;
  }
  int size(int x) {
    return siz[find(x)];
  }
  void rollback() {
    if (!st.empty()) {
      int x = st.back();
      st.pop_back();
      siz[f[x]] -= siz[x];
      f[x] = x;
    }
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, m;
  cin >> n >> m;
  vector<array<int, 3>> e;
  for (int i = 0; i < m; i++) {
    int u, v, d;
    cin >> u >> v >> d;
    --u;
    --v;
    e.push_back({u, v, d});
  }
  int q;
  cin >> q;
  vector<array<int, 3>> Q(q);
  for (int i = 0; i < q; i++) {
    cin >> Q[i][0] >> Q[i][1] >> Q[i][2];
    Q[i][1]--;
  }
  vector<int> ans(q);
  for (int L = 0; L < q; L += B) {
    vector<int> mark(m);
    vector<int> same;
    vector<int> diff;
    vector<int> t2;
    int R = min(L + B, q);
    for (int i = L; i < R; i++) {
      if (Q[i][0] == 1) {
        mark[Q[i][1]] = 1;
        diff.push_back(Q[i][1]);
      } else {
        t2.push_back(i);
      }
    }
    vector<vector<int>> c(B);
    for (int i = L; i < R; i++) {
      if (Q[i][0] == 1) {
        e[Q[i][1]][2] = Q[i][2];
      } else {
        for (int j : diff) {
          if (e[j][2] >= Q[i][2]) {
            c[i - L].push_back(j);
          }
        }
      }
    }
    for (int i = 0; i < m; i++) {
      if (!mark[i]) {
        same.push_back(i);
      }
    }
    sort(t2.begin(), t2.end(), [&](int i, int j) {
      return Q[i][2] > Q[j][2];
    });
    sort(same.begin(), same.end(), [&](int i, int j) {
      return e[i][2] > e[j][2];
    });
    DSU d(n);
    int ptr = 0;
    for (int i : t2) {
      while (ptr < (int) same.size() && e[same[ptr]][2] >= Q[i][2]) {
        d.merge(e[same[ptr]][0], e[same[ptr]][1]);
        ptr++;
      }
      int cnt = 0;
      for (int j : c[i - L]) {
        if (d.merge(e[j][0], e[j][1])) {
          cnt++;
        }
      }
      ans[i] = d.size(Q[i][1]);
      while (cnt--) {
        d.rollback();
      }
    }
  }
  for (int i = 0; i < q; i++) {
    if (Q[i][0] == 2) {
      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