Submission #554969

#	Time	Username	Problem	Language	Result	Execution time	Memory
554969		Sweezy	Bridges (APIO19_bridges)	C++17	100 / 100	2420 ms	31000 KiB

bridges

#include <bits/stdc++.h>

using namespace std;
#define int long long

struct DSU {
  int n;
  vector<int> p, s;
  DSU(int n): n(n), p(n), s(n) {
    iota(p.begin(), p.end(), 0);
    fill(s.begin(), s.end(), 1);
  };

  int get(int v) {
    return (p[v] == v ? v : p[v] = get(p[v]));
  }

  void unite(int a, int b) {
    a = get(a), b = get(b);
    if (a != b) {
      if (s[a] > s[b]) swap(a, b);
      p[b] = a;
      s[a] += s[b];
    }
  }
};

const int B = 800;

void solve() {
  int n, m;
  cin >> n >> m;
  vector<array<int, 4>> edges(m);
  for (int i = 0; i < m; i++) {
    cin >> edges[i][0] >> edges[i][1] >> edges[i][2];
    --edges[i][0], --edges[i][1];
    edges[i][3] = i;
  }

  auto sorted = edges;
  sort(sorted.begin(), sorted.end(), [&] (const array<int, 4>& lhs, const array<int, 4>& rhs) {
    return lhs[2] > rhs[2];
  });

  int q;
  cin >> q;
  int cnt_blocks = (q + B - 1) / B;
  vector<vector<array<int, 3>>> qchange(cnt_blocks), qask(cnt_blocks);
  for (int i = 0; i < q; i++) {
    int t, a, b;
    cin >> t >> a >> b;
    if (t == 1) {
      qchange[i / B].push_back({a - 1, b, i});
    } else {
      qask[i / B].push_back({a - 1, b, i});
    }
  }

  vector<pair<int, int>> answer;
  for (int block = 0; block < cnt_blocks; block++) {
    reverse(qchange[block].begin(), qchange[block].end());
    sort(qask[block].begin(), qask[block].end(), [&] (const array<int, 3>& lhs, const array<int, 3>& rhs) {
      return lhs[1] > rhs[1];
    });

    vector<char> in(m), changed(m), used(n);
    for (auto &[edge, lol, kek] : qchange[block]) {
      in[edge] = 1;
    }

    DSU dsu(n);
    int ptr = -1;
    vector<vector<int>> g(n);
    for (auto &[s, w, i] : qask[block]) {
      while (ptr + 1 < m && sorted[ptr + 1][2] >= w) {
        ptr++;
        if (in[sorted[ptr][3]] == 1) {
          continue;
        }
        dsu.unite(sorted[ptr][0], sorted[ptr][1]);
      }
      for (auto &[edge, weight, id] : qchange[block]) {
        if (id <= i && changed[edge] == 0) {
          changed[edge] = 1;
          if (weight >= w) {
            g[dsu.get(edges[edge][0])].push_back(dsu.get(edges[edge][1]));
            g[dsu.get(edges[edge][1])].push_back(dsu.get(edges[edge][0]));
          }
        }
      }
      for (auto &[edge, weight, id] : qchange[block]) {
        if (id > i && changed[edge] == 0) {
          changed[edge] = 1;
          if (edges[edge][2] >= w) {
            g[dsu.get(edges[edge][0])].push_back(dsu.get(edges[edge][1]));
            g[dsu.get(edges[edge][1])].push_back(dsu.get(edges[edge][0]));
          }
        }
      }


      int res = 0;
      vector<int> vert;
      function<void(int)> dfs = [&] (int v) {
        used[v] = 1;
        res += dsu.s[v];
        vert.push_back(v);
        for (auto &u : g[v]) {
          if (!used[u]) {
            dfs(u);
          }
        }
      };
      dfs(dsu.get(s));
      for (auto &v : vert) {
        used[v] = 0;
      }

      for (auto &[edge, weight, id] : qchange[block]) {
        changed[edge] = 0;
        g[dsu.get(edges[edge][0])].clear();
        g[dsu.get(edges[edge][1])].clear();
      }

      answer.emplace_back(i, res);
    }

    vector<pair<int, int>> changes;
    for (auto &[edge, weight, id] : qchange[block]) {
      if (changed[edge] == 0) {
        changed[edge] = 1;
        edges[edge][2] = weight;
        changes.emplace_back(weight, edge);
      }
    }
    sort(changes.rbegin(), changes.rend());

    int chng = 0;
    vector<array<int, 4>> new_sorted;
    for (int i = 0; i < m; i++) {
      while (chng < (int) changes.size() && changes[chng].first >= sorted[i][2]) {
        new_sorted.push_back(edges[changes[chng].second]);
        chng++;
      }
      if (in[sorted[i][3]] == 0) {
        new_sorted.push_back(sorted[i]);
      }
    }

    while (chng < (int) changes.size()) {
      new_sorted.push_back(edges[changes[chng].second]);
      chng++;
    }

    swap(sorted, new_sorted);
  }

  sort(answer.begin(), answer.end());
  for (auto &[i, res] : answer) {
    cout << res << '\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