Submission #1063291

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063291		nima_aryan	Bridges (APIO19_bridges)	C++17	100 / 100	1520 ms	133420 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() {
    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;
};

constexpr int T = 1000;

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

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

  int q;
  cin >> q;

  vector<int> t(q), x(q), y(q);
  for (int i = 0; i < q; ++i) {
    cin >> t[i] >> x[i] >> y[i];
    --x[i];
  }

  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<int> ask;
    for (int i = l; i < r; ++i) {
      if (t[i] == 1) {
        d[x[i]] = y[i];
        changed[x[i]] = true;
      } else {
        for (int j = l; j < r; ++j) {
          if (t[j] == 1 && d[x[j]] >= y[i]) {
            to_join[i].push_back(x[j]);
          }
        }
        ask.push_back(i);
      }
    }
    vector<int> unchanged;
    for (int i = 0; i < m; ++i) {
      if (!changed[i]) {
        unchanged.push_back(i);
      }
    }
    sort(unchanged.begin(), unchanged.end(), [&](int i, int j) {
      return d[i] > d[j];
    });
    sort(ask.begin(), ask.end(), [&](int i, int j) {
      return y[i] > y[j];
    });
    PersistentDsu dsu(n);
    int p = 0;
    for (int i : ask) {
      for (; p < unchanged.size(); ++p) {
        int e = unchanged[p];
        if (d[e] >= y[i]) {
          dsu.unite(u[e], v[e]);
        } else {
          break;
        }
      }
      dsu.persist();
      for (int e : to_join[i]) {
        dsu.unite(u[e], v[e]);
      }
      ans[i] = dsu.size(x[i]);
      dsu.rollback();
    }
  }

  for (int i = 0; i < q; ++i) {
    if (t[i] == 2) {
      cout << ans[i] << "\n";
    }
  }

  return 0;
}

Compilation message (stderr)

bridges.cpp: In member function 'void PersistentDsu::rollback()':
bridges.cpp:49: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]
   49 |     while (stk.size() > snap.back()) {
      |            ~~~~~~~~~~~^~~~~~~~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:122:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |       for (; p < unchanged.size(); ++p) {
      |              ~~^~~~~~~~~~~~~~~~~~

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