Submission #967021

#	Time	Username	Problem	Language	Result	Execution time	Memory
967021		kilkuwu	Bridges (APIO19_bridges)	C++17	100 / 100	1827 ms	12252 KiB

bridges

#include <bits/stdc++.h>

#define nl '\n'

#ifdef LOCAL
#include "template/debug.hpp"
#else
#define dbg(...) ;
#define timer(...) ;
#endif

struct DSU {
  std::vector<int> e;
  std::vector<std::array<int, 4>> trace;

  DSU(int n) : e(n, -1) {}

  int find(int u) {
    return e[u] < 0 ? u : find(e[u]);
  }
  
  bool merge(int u, int v) {
    trace.push_back({-1, -1, -1, -1});
    u = find(u), v = find(v);
    if (u == v) return false;
    if (e[u] > e[v]) std::swap(u, v);
    trace.back() = {u, e[u], v, e[v]};
    e[u] += e[v];
    e[v] = u;
    return true;
  } 

  void rollback() {
    auto [u, eu, v, ev] = trace.back();
    trace.pop_back();
    if (u != -1) {
      e[u] = eu;
      e[v] = ev;
    }
  }

  void rollback(int size) {
    while ((int) trace.size() > size) {
      rollback(); 
    }
  }

  int history_size() const {
    return trace.size();
  }

  bool same(int u, int v) {
    return find(u) == find(v);
  }
  
  int size(int u) {
    return -e[find(u)];
  }
};

struct Edge {
  int u, v, d, i;

  bool operator<(const Edge& rhs) const {
    return d < rhs.d;
  }
};



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

  int n, m; 
  std::cin >> n >> m;

  std::vector<std::array<int, 3>> edges(m);
  for (int i = 0; i < m; i++) {
    int u, v, d;
    std::cin >> u >> v >> d;
    --u, --v;
    edges[i] = {d, u, v};
  }

  int q;
  std::cin >> q;
  std::vector<int> ans(q, -1);
  const int B = 1000;
  std::vector<int> is_changed(m, -1);
  std::vector<int> become(m, -1);

  std::vector<std::array<int, 3>> unchanged;
  std::vector<int> changed;
  unchanged.reserve(m);
  changed.reserve(m);

  for (int lb = 0; lb < q; lb += B) {
    int rb = std::min(lb + B, q);
    std::vector<std::array<int, 3>> ask;
    std::vector<std::array<int, 3>> upd;
    for (int i = lb; i < rb; i++) {
      int t, a, b;
      std::cin >> t >> a >> b;
      --a;
      if (t == 1) {
        is_changed[a] = lb;
        upd.push_back({b, a, i});
      } else {
        ask.push_back({b, a, i}); 
      }
    }

    unchanged.clear();
    changed.clear();
    for (int i = 0; i < m; i++) {
      if (is_changed[i] < lb) {
        unchanged.emplace_back(edges[i]);
      } else {
        changed.emplace_back(i);
      }
    }


    std::sort(unchanged.rbegin(), unchanged.rend());

    DSU dsu(n);


    int j = 0;
    std::sort(ask.rbegin(), ask.rend()); 


    for (auto [w, s, id] : ask) {
      while (j < (int) unchanged.size() && unchanged[j][0] >= w) {
        dsu.merge(unchanged[j][1], unchanged[j][2]);
        j++;
      }

      int sz = dsu.history_size();

      for (auto [r, b, uid] : upd) {
        if (uid <= id) {
          become[b] = r;
        }
      }

      for (int i : changed) {
        auto [d, u, v] = edges[i];
        if (become[i] != -1) d = become[i];
        if (d >= w) {
          dsu.merge(u, v);
        }
      }

      for (auto [r, b, uid] : upd) {
        if (uid <= id) {
          become[b] = -1;
        }
      }

      ans[id] = dsu.size(s);
      
      dsu.rollback(sz);
    }

    for (auto [r, b, uid] : upd) {
      edges[b][0] = r;
    }
  }

  for (int i = 0; i < q; i++) {
    if (ans[i] != -1) std::cout << ans[i] << nl;
  }
}

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