Submission #683717

#	Time	Username	Problem	Language	Result	Execution time	Memory
683717		evenvalue	Bridges (APIO19_bridges)	C++17	0 / 100	1064 ms	12280 KiB

bridges

#include <bits/stdc++.h>
using namespace std;

#ifdef evenvalue
  #include "debug.h"
  #define debug(...) print(#__VA_ARGS__, __VA_ARGS__)
#else
  #define debug(...)
#endif

using int64 = long long;
using ld = long double;

template<typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using max_heap = priority_queue<T, vector<T>, less<T>>;

namespace read {
int Int() {
  int x;
  cin >> x;
  return x;
}
}//namespace read

constexpr int kInf = 1e9 + 10;
constexpr int64 kInf64 = 1e15 + 10;
constexpr int kMod = 1e9 + 7;
constexpr int kBlockSize = 400;

class dsu {
  int n;
  std::vector<int> e;
  vector<pair<int, int>> history;

  int pfind(const int x) {
    return (e[x] < 0 ? x : pfind(e[x]));
  }

public:
  dsu() : n(0), comp(0) {}
  explicit dsu(const int n) : n(n), comp(n), e(n, -1) {}

  int comp;

  int find(const int x) {
    assert(0 <= x and x < n);
    return pfind(x);
  }

  bool unite(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) {
      history.emplace_back(kInf, kInf);
      return false;
    }
    if (e[x] > e[y]) swap(x, y);
    history.emplace_back(y, e[y]);
    e[x] += e[y];
    e[y] = x;
    comp--;
    return true;
  }

  bool rollback() {
    if (history.empty()) return false;
    if (history.back().second != kInf) {
      const int y = history.back().first;
      const int x = find(y);
      e[x] -= history.back().second;
      e[y] = history.back().second;
    }
    history.pop_back();
    return true;
  }

  bool same(const int x, const int y) {
    return (find(x) == find(y));
  }

  int size(const int x) {
    return -e[find(x)];
  }

  std::vector<std::vector<int>> components() {
    std::vector<std::vector<int>> res(n);
    for (int x = 0; x < n; x++) {
      res[pfind(x)].push_back(x);
    }
    res.erase(
        std::remove_if(res.begin(), res.end(), [&](const std::vector<int> &v) { return v.empty(); }),
        res.end()
    );
    return res;
  }
};

inline void solution() {
  struct update {
    int index;
    int bridge;
    int limit;
  };

  struct query {
    int index;
    int weight;
    int source;
  };

  struct bridge {
    int x = -1;
    int y = -1;
    int w = -1;
    bool change = false;
  };

  const int n = read::Int();
  const int m = read::Int();

  vector<bridge> bridges(m);
  for (int i = 0; i < m; i++) {
    bridges[i].x = read::Int() - 1;
    bridges[i].y = read::Int() - 1;
    bridges[i].w = read::Int();
  }

  vector<vector<update>> blocks = {{}};
  vector<query> queries;

  const int qq = read::Int();
  for (int i = 0; i < qq; i++) {
    const int t = read::Int();
    if (t == 1) {
      update cur{};
      cur.index = i;
      cur.bridge = read::Int() - 1;
      cur.limit = read::Int();
      blocks.back().push_back(cur);
    } else {
      query cur{};
      cur.index = i;
      cur.source = read::Int() - 1;
      cur.weight = read::Int();
      queries.push_back(cur);
    }
    if (blocks.back().size() == kBlockSize) blocks.emplace_back();
  }

  blocks.back().push_back({qq, -1, kInf});

  vector<int> ans(qq);
  for (int i = 0, j = 0; i < blocks.size(); i++) {
    const vector<update> &block = blocks[i];
    const int last_index = block.back().index;

    vector<query> q;
    for (; j < queries.size(); j++) {
      if (queries[j].index > last_index) break;
      q.push_back(queries[j]);
    }

    sort(q.begin(), q.end(), [&](const query &q1, const query &q2) {
      return q1.weight > q2.weight;
    });

    vector<bridge> edges = bridges;
    for (const update &u : block) {
      if (u.index == -1) continue;
      edges[u.bridge].change = true;
    }

    sort(edges.begin(), edges.end(), [&](const bridge &e1, const bridge &e2) {
      return e1.w > e2.w;
    });

    dsu d(n);
    for (int qry = 0, edge = 0; qry < q.size(); qry++) {
//      const auto [index, weight, source] = q[qry];
      const int index = q[qry].index;
      const int weight = q[qry].weight;
      const int source = q[qry].source;

      while (edge < edges.size() and edges[edge].w >= weight) {
        if (not edges[edge].change) {
          d.unite(edges[edge].x, edges[edge].y);
        }
        edge++;
      }

      int rollbacks = 0;
      for (const update &u : block) {
        if (u.index == qq) continue;
        const auto [x, y, w, _] = bridges[u.bridge];
        if (u.index < index and weight <= u.limit) {
          rollbacks++;
          d.unite(x, y);
        }
        if (u.index > index and weight <= w) {
          rollbacks++;
          d.unite(x, y);
        }
      }

      ans[index] = d.size(source);
      while (rollbacks--) {
        assert(d.rollback());
      }
    }
  }

  for (const query q : queries) {
    cout << ans[q.index] << '\n';
  }
}


int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  cout << fixed << setprecision(10);

  int testcases = 1;
  //cin >> testcases;
  while (testcases--) {
    solution();
  }
}

Compilation message (stderr)

bridges.cpp: In constructor 'dsu::dsu(int)':
bridges.cpp:45:7: warning: 'dsu::comp' will be initialized after [-Wreorder]
   45 |   int comp;
      |       ^~~~
bridges.cpp:34:20: warning:   'std::vector<int> dsu::e' [-Wreorder]
   34 |   std::vector<int> e;
      |                    ^
bridges.cpp:43:12: warning:   when initialized here [-Wreorder]
   43 |   explicit dsu(const int n) : n(n), comp(n), e(n, -1) {}
      |            ^~~
bridges.cpp: In function 'void solution()':
bridges.cpp:154:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<solution()::update> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |   for (int i = 0, j = 0; i < blocks.size(); i++) {
      |                          ~~^~~~~~~~~~~~~~~
bridges.cpp:159:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<solution()::query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |     for (; j < queries.size(); j++) {
      |            ~~^~~~~~~~~~~~~~~~
bridges.cpp:179:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<solution()::query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  179 |     for (int qry = 0, edge = 0; qry < q.size(); qry++) {
      |                                 ~~~~^~~~~~~~~~
bridges.cpp:185:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<solution()::bridge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  185 |       while (edge < edges.size() and edges[edge].w >= weight) {
      |              ~~~~~^~~~~~~~~~~~~~

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