Submission #1172933

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172933		fryingduc	다리 (APIO19_bridges)	C++20	100 / 100	2597 ms	4776 KiB

bridges

#include "bits/stdc++.h"

using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 5e4 + 4;
const int M = 1e5 + 5;
const int B = 450;

int n, m, q;
int eu[M], ev[M], ew[M];
int qo[M], qu[M], qv[M];
bool mark[M];
int lab[maxn];
stack<pair<int, int>> stk;
int lt[M];
int res[M];

int find(int u) {
  return lab[u] < 0 ? u : find(lab[u]);
}

void join(int u, int v, bool rb) {
  u = find(u), v = find(v);
  if (u == v) return;
  if (lab[u] > lab[v]) swap(u, v);
  if (rb) stk.push(make_pair(v, lab[v]));
  lab[u] += lab[v];
  lab[v] = u;
}

void rollback() {
  while (!stk.empty()) {
    auto [v, l] = stk.top();
    stk.pop();
    lab[lab[v]] -= l;
    lab[v] = l;
  }
}

void solve() {
  cin >> n >> m;
  for (int i = 1; i <= m; ++i) {
    cin >> eu[i] >> ev[i] >> ew[i];
  }
  cin >> q;
  for (int i = 1; i <= q; ++i) {
    cin >> qo[i] >> qu[i] >> qv[i];
  }
  for (int st = 1; st <= q; st += B) {
    int en = min(q, st + B - 1);
    vector<int> aft;
    vector<int> que;
    vector<int> eg;
    for (int i = st; i <= en; ++i) {
      if (qo[i] == 1) {
        mark[qu[i]] = 1;
      } else {
        que.push_back(i);
      }
    }
    for (int i = 1; i <= m; ++i) {
      if (!mark[i]) {
        aft.push_back(i);
      } else {
        eg.push_back(i);
      }
    }
    sort(aft.begin(), aft.end(), [](const int &x, const int &y) -> bool {
      return ew[x] > ew[y];
    });
    sort(que.begin(), que.end(), [](const int &x, const int &y) -> bool {
      return qv[x] > qv[y];
    });
    memset(lab, -1, sizeof(lab));
    int ptr = 0;
    for (int i = 0; i < (int)que.size(); ++i) {
      while (ptr < (int)aft.size() and ew[aft[ptr]] >= qv[que[i]]) {
        join(eu[aft[ptr]], ev[aft[ptr]], 0);
        ++ptr;
      }
      for (int j = st; j < que[i]; ++j) {
        if (qo[j] == 1) {
          lt[qu[j]] = j;
        }
      }
      for (auto j : eg) {
        if (lt[j]) {
          if (qv[lt[j]] >= qv[que[i]]) {
            join(eu[j], ev[j], 1);
          }
        } else {
          if (ew[j] >= qv[que[i]]) {
            join(eu[j], ev[j], 1);
          }
        }
      }
      res[que[i]] = -lab[find(qu[que[i]])];
      rollback();
      for (int j = st; j < que[i]; ++j) {
        if (qo[j] == 1) {
          lt[qu[j]] = 0;
        }
      }
    }
    for (int i = st; i <= en; ++i) {
      if (qo[i] == 1) {
        ew[qu[i]] = qv[i];
        mark[qu[i]] = 0;
      }
    }
  }
  for (int i = 1; i <= q; ++i) {
    if (qo[i] == 2) {
      cout << res[i] << '\n';
    }
  }
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  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