Submission #1150271

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150271		abczz	Bridges (APIO19_bridges)	C++20	59 / 100	3085 ms	417360 KiB

bridges

#include <iostream>
#include <array>
#include <algorithm>
#include <cmath>
#define ll int
using namespace std;

array<ll, 3> A[100005];
vector <array<ll, 4>> Q;
vector <array<ll, 4>> T;
vector <ll> U[100005];
ll n, m, q, a, b, c, t, rtq, P[100005], F[100005];

struct DSU{
  vector <ll> G, gsz;
  void init(ll sz) {
    G.resize(sz);
    gsz.resize(sz);
    for (int i=0; i<sz; ++i) G[i] = i, gsz[i] = 1;
  }
  ll dsu(ll u) {
    if (G[u] == u) return u;
    else return dsu(G[u]);
  }
  ll dsu_fast(ll u) {
    if (G[u] == u) return u;
    else return G[u] = dsu(G[u]);
  }
  ll query(ll u) {
    return gsz[dsu(u)];
  }
  void merge(ll a, ll b, bool x) {
    ll u, v;
    if (!x) u = dsu_fast(a), v = dsu_fast(b);
    else u = dsu(a), v = dsu(b);
    if (u == v) return;
    if (gsz[u] > gsz[v]) swap(u, v);
    if (x) T.push_back({u, G[u], v, gsz[v]});
    G[u] = v, gsz[v] += gsz[u];
  }
  void rollback() {
    while (!T.empty()) {
      auto u = T.back();
      T.pop_back();
      G[u[0]] = u[1], gsz[u[2]] = u[3];
    }
  }
}block[400];
int main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  cin >> n >> m;
  for (int i=0; i<m; ++i) {
    for (int j=0; j<3; ++j) {
      cin >> A[i][j];
    }
    --A[i][0], --A[i][1];
  }
  cin >> q;
  rtq = sqrt(q);
  for (int i=0; i<=q/rtq; ++i) {
    block[i].init(n);
  }
  for (int i=1; i<=q; ++i) {
    cin >> a >> b >> c;
    --b;
    if (a == 1) {
      Q.push_back({A[b][2], b, P[b], i-1});
      P[b] = i, A[b][2] = c;
    }
    else {
      F[t] = b;
      Q.push_back({c, -1, i, t++});
    }
  }
  for (int i=0; i<m; ++i) {
    Q.push_back({A[i][2], i, P[i], q});
  }
  sort(Q.begin(), Q.end(), [](auto a, auto b) {
    return a > b;
  });
  for (auto [u, id, l, r] : Q) {
    if (id != -1) {
      a = ((l-1) / rtq)+1;
      b = r / rtq;
      if (r == q) ++b;
      for (int i=l; i<min(a*rtq, r+1); ++i) {
        U[i].push_back(id);
      }
      for (int i=a; i<b; ++i) {
        block[i].merge(A[id][0], A[id][1], 0);
      }
      for (int i=max(min(a*rtq, r+1), b*rtq); i<=r; ++i) {
        U[i].push_back(id);
      }
    }
    else {
      ll x = l/rtq;
      for (auto id : U[l]) {
        block[x].merge(A[id][0], A[id][1], 1);
      }
      F[r] = block[x].query(F[r]);
      block[x].rollback();
    }
  }
  for (int i=0; i<t; ++i) cout << F[i] << '\n';
}

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