제출 #1363568

#제출 시각아이디문제언어결과실행 시간메모리
1363568edoBridges (APIO19_bridges)C++20
100 / 100
1600 ms5912 KiB
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

struct E {
  int u, v;
  ll w;
};

struct RollbackDSU {
  int n;
  vector<int> p, sz;
  vector<int> st;

  RollbackDSU(int n = 0) { init(n); }

  void init(int n_) {
    n = n_;
    p.resize(n + 1);
    sz.assign(n + 1, 1);
    iota(p.begin(), p.end(), 0);
    st.clear();
  }

  int find(int a) {
    while (p[a] != a)
      a = p[a];
    return a;
  }

  void unite(int a, int b) {
    a = find(a), b = find(b);
    if (a == b)
      return;
    if (sz[a] > sz[b])
      swap(a, b);
    st.push_back(a);
    sz[b] += sz[a];
    p[a] = b;
  }

  int snapshot() { return (int)st.size(); }

  void rollback(int snap) {
    while ((int)st.size() > snap) {
      int a = st.back();
      st.pop_back();
      int b = p[a];
      sz[b] -= sz[a];
      p[a] = a;
    }
  }

  int compSize(int a) { return sz[find(a)]; }
};

struct Q {
  int t, a, b, id;
};

using TT = tuple<int, int, int, vector<int>>;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m;
  cin >> n >> m;
  vector<E> e(m + 1);
  for (int i = 1, u, v; i <= m; ++i) {
    cin >> e[i].u >> e[i].v >> e[i].w;
  }

  int qq;
  cin >> qq;
  vector<Q> q;
  vector<int> ans;
  q.reserve(qq);
  for (int i = 0, t, a, b; i < qq; ++i) {
    cin >> t >> a >> b, t--;
    if (t)
      q.push_back({t, a, b, (int)ans.size()}), ans.push_back(0);
    else
      q.push_back({t, a, b, -1});
  }

  const int B = 700;
  for (int l = 0; l < qq; l += B) {
    int r = min(qq, l + B);
    vector<int> change, pos(m + 1, -1);
    for (int i = l; i < r; ++i) {
      if (!q[i].t) {
        int ee = q[i].a;
        if (!~pos[ee]) {
          pos[ee] = change.size();
          change.emplace_back(ee);
        }
      }
    }
    int k = change.size();
    vector<int> normal;
    normal.reserve(m);
    for (int ee = 1; ee <= m; ++ee)
      if (!~pos[ee])
        normal.push_back(ee);

    sort(normal.begin(), normal.end(),
         [&](int x, int y) { return e[x].w > e[y].w; });
    vector<int> cur(k);
    for (int i = 0; i < k; ++i) {
      cur[i] = e[change[i]].w;
    }
    vector<TT> ask;
    for (int i = l; i < r; ++i) {
      if (!q[i].t) {
        int ee = q[i].a;
        cur[pos[ee]] = q[i].b;
      } else {
        int s = q[i].a, w = q[i].b, id = q[i].id;
        ask.push_back({s, w, id, cur});
      }
    }
    sort(ask.begin(), ask.end(),
         [&](const TT &x, const TT &y) { return get<1>(x) > get<1>(y); });
    RollbackDSU dsu(n);
    int ptr = 0;
    for (auto &A : ask) {
      while (ptr < normal.size() && e[normal[ptr]].w >= get<1>(A)) {
        int ee = normal[ptr];
        dsu.unite(e[ee].u, e[ee].v);
        ptr++;
      }
      int snp = dsu.snapshot();
      for (int i = 0; i < k; ++i) {
        if (get<3>(A)[i] >= get<1>(A)) {
          int ee = change[i];
          dsu.unite(e[ee].u, e[ee].v);
        }
      }
      ans[get<2>(A)] = dsu.compSize(get<0>(A));
      dsu.rollback(snp);
    }

    for (int i = l; i < r; ++i) {
      if (!q[i].t) {
        int ee = q[i].a;
        e[ee].w = q[i].b;
      }
    }
  }
  for (auto x : ans)
    cout << x << "\n";

  return 0;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…