Submission #1228636

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228636		kunzaZa183	Bridges (APIO19_bridges)	C++20	59 / 100	3091 ms	28344 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
int main() {
  int n, m;
  cin >> n >> m;
  vector<int> u(m), v(m), w(m);
  for (int i = 0; i < m; i++) {
    cin >> u[i] >> v[i] >> w[i];
    u[i]--, v[i]--;
  }

  int qs;
  cin >> qs;

  vector<int> type(qs), x1(qs), x2(qs);
  for (int i = 0; i < qs; i++) {
    cin >> type[i] >> x1[i] >> x2[i];
    x1[i]--;
  }

  const int k = 316;

  vector<vector<int>> vvi(qs), adj(n);
  vector<int> tmpw(m), ans(qs, -1);
  vector<bool> visited(n);
  for (int chunk = 0; chunk * k < qs; chunk++) {
    vector<bool> changed(m, 0);
    vector<int> cureffects, ch, qries;
    for (int i = chunk * k; i < qs && i < (chunk + 1) * k; i++)
      if (type[i] == 1) {
        changed[x1[i]] = 1;
        ch.push_back(x1[i]);
        cureffects.push_back(i);
      } else {
        vvi[i] = cureffects;
        qries.push_back(i);
      }

    vector<int> noch;
    for (int i = 0; i < m; i++)
      if (!changed[i])
        noch.push_back(i);

    sort(noch.begin(), noch.end(), [&](int a, int b) { return w[a] > w[b]; });
    sort(qries.begin(), qries.end(),
         [&](int a, int b) { return x2[a] > x2[b]; });

    vector<int> dsu(n), sz(n, 1);
    iota(dsu.begin(), dsu.end(), 0);

    auto par = [&](int in, auto &&sth) {
      if (dsu[in] == in)
        return in;
      return dsu[in] = sth(dsu[in], sth);
    };

    int nochin = 0;
    for (auto a : qries) {
      while (nochin < noch.size() && (w[noch[nochin]] >= x2[a])) {
        if (par(u[noch[nochin]], par) != par(v[noch[nochin]], par)) {
          sz[par(u[noch[nochin]], par)] += sz[par(v[noch[nochin]], par)];
          dsu[par(v[noch[nochin]], par)] = par(u[noch[nochin]], par);
        }
        nochin++;
      }

      for (auto b : ch)
        tmpw[b] = w[b];

      for (auto b : vvi[a]) {
        tmpw[x1[b]] = x2[b];
      }

      for (auto b : ch)
        if (tmpw[b] >= x2[a]) {
          adj[par(u[b], par)].push_back(par(v[b], par));
          adj[par(v[b], par)].push_back(par(u[b], par));
        }

      vector<int> visivi;
      vector<int> tmpvi2 = {par(x1[a], par)};
      while (!tmpvi2.empty()) {
        int ok = tmpvi2.back();
        tmpvi2.pop_back();

        if (visited[ok])
          continue;

        visited[ok] = 1;
        visivi.push_back(ok);

        for (auto b : adj[ok])
          tmpvi2.push_back(b);
      }

      for (auto b : ch)
        if (tmpw[b] >= x2[a]) {
          adj[par(u[b], par)].clear(), adj[par(v[b], par)].clear();
        }

      ans[a] = 0;
      for (auto b : visivi) {
        ans[a] += sz[b];
        visited[b] = 0;
      }
    }

    for (auto a : cureffects)
      w[x1[a]] = x2[a];
  }

  for (auto a : ans)
    if (a != -1)
      cout << a << "\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