Submission #1063271

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063271		nima_aryan	Bridges (APIO19_bridges)	C++17	100 / 100	1521 ms	132920 KiB

bridges

/**
 *    author:  NimaAryan
 *    created: 2024-08-17 18:01:24  
**/
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#endif

using i64 = long long;

struct PersistentDsu {
  vector<int> p;

  PersistentDsu(int n) {
    p.assign(n, -1);
  }

  int get(int x) {
    return p[x] < 0 ? x : get(p[x]);
  }

  int size(int x) {
    return -p[get(x)];
  }

  vector<int> snap;
  vector<pair<int, int>> stk;
  bool unite(int x, int y) {
    x = get(x), y = get(y);
    if (x == y) {
      return false;
    }
    if (size(x) < size(y)) {
      swap(x, y);
    }
    stk.emplace_back(y, p[y]);
    p[x] += p[y];
    p[y] = x;
    return true;
  }
  void persist() {
    snap.push_back(stk.size());
  }
  void rollback() {
    assert(!snap.empty());
    while (stk.size() > snap.back()) {
      auto [y, z] = stk.back();
      stk.pop_back();
      int x = p[y];
      p[x] -= z;
      p[y] = z;
    }
    snap.pop_back();
  }
};

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

struct Query {
  int t;
  int b, r;
  int s, w;
  int x;
  int ans;
};

constexpr int T = 1000;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  
  int n, m;
  cin >> n >> m;

  vector<Edge> e(m);
  for (auto& [u, v, d] : e) {
    cin >> u >> v >> d;
    --u, --v;
  }

  int q;
  cin >> q;

  vector<Query> qs(q);
  for (auto& qi : qs) {
    cin >> qi.t;
    if (qi.t == 1) {
      cin >> qi.b >> qi.r;
      --qi.b;
    } else {
      cin >> qi.s >> qi.w;
      --qi.s;
    }
  }

  vector<int> ans(q);
  vector<vector<int>> to_join(q);
  for (int l = 0; l < q; l += T) {
    int r = min(q, l + T);
    vector<bool> changed(m);
    vector<Query> ask;
    for (int x = l; x < r; ++x) {
      auto& qi = qs[x];
      qi.x = x;
      if (qi.t == 1) {
        e[qi.b].d = qi.r;
        changed[qi.b] = true;
      } else {
        for (int y = l; y < r; ++y) {
          auto& qj = qs[y];
          if (qj.t == 1 && e[qj.b].d >= qi.w) {
            to_join[x].push_back(qj.b);
          }
        }
        ask.push_back(qi);
      }
    }
    vector<int> c;
    for (int i = 0; i < m; ++i) {
      if (!changed[i]) {
        c.push_back(i);
      }
    }
    sort(c.begin(), c.end(), [&](int i, int j) {
      return e[i].d > e[j].d;
    });
    sort(ask.begin(), ask.end(), [&](auto qi, auto qj) {
      return qi.w > qj.w;
    });
    PersistentDsu dsu(n);
    int p = 0;
    for (auto& qi : ask) {
      while (p < c.size() && e[c[p]].d >= qi.w) {
        dsu.unite(e[c[p]].u, e[c[p]].v);
        ++p;
      }
      dsu.persist();
      for (int i : to_join[qi.x]) {
        dsu.unite(e[i].u, e[i].v);
      }
      qs[qi.x].ans = dsu.size(qi.s);
      dsu.rollback();
    }
  }

  for (auto& qi : qs) {
    if (qi.t == 2) {
      cout << qi.ans << "\n";
    }
  }

  return 0;
}

Compilation message (stderr)

bridges.cpp: In member function 'void PersistentDsu::rollback()':
bridges.cpp:50:23: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} [-Wsign-compare]
   50 |     while (stk.size() > snap.back()) {
      |            ~~~~~~~~~~~^~~~~~~~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:140:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |       while (p < c.size() && e[c[p]].d >= qi.w) {
      |              ~~^~~~~~~~~~

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