lmori's Library

This documentation is automatically generated by competitive-verifier/competitive-verifier

View the Project on GitHub lmorinn/library

:heavy_check_mark: verify/AizuOnlineJudge/graph/connectivity/GraphConstruction2235.test.cpp

Depends on

Code

#include "../../../../template/template.hpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2235"
#include "../../../../graph/connectivity/OfflineDynamicConnectivityDFS.hpp"

using S = int;

S op(S a, S b) {
  return a + b;
}

S e() {
  return 0;
}
int main() {
  cin.tie(0)->sync_with_stdio(0);
  int n, q;
  in(n, q);
  OfflineDynamicConnectivity<S, op, e> g(n);

  rep(i, q) {
    int com, u, v;
    in(com, u, v);
    if (com == 1) {
      g.link(u, v);
    } else if (com == 2) {
      g.cut(u, v);
    } else if (com == 3) {
      g.is_connected(u, v);
    }
  }

  for (auto x : g.build()) {
    out(x ? "YES" : "NO");
  }
}
#line 2 "template/template.hpp"
#pragma region Macros
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using ull = unsigned long long;
using ld = long double;
using int128 = __int128_t;
#define all(x) (x).begin(), (x).end()
#define uniqv(v) v.erase(unique(all(v)), v.end())
#define OVERLOAD_REP(_1, _2, _3, name, ...) name
#define REP1(i, n) for (auto i = std::decay_t<decltype(n)>{}; (i) != (n); ++(i))
#define REP2(i, l, r) for (auto i = (l); (i) != (r); ++(i))
#define rep(...) OVERLOAD_REP(__VA_ARGS__, REP2, REP1)(__VA_ARGS__)
#define logfixed(x) cout << fixed << setprecision(10) << x << endl;

ostream &operator<<(ostream &dest, __int128_t value) {
  ostream::sentry s(dest);
  if (s) {
    __uint128_t tmp = value < 0 ? -value : value;
    char buffer[128];
    char *d = end(buffer);
    do {
      --d;
      *d = "0123456789"[tmp % 10];
      tmp /= 10;
    } while (tmp != 0);
    if (value < 0) {
      --d;
      *d = '-';
    }
    int len = end(buffer) - d;
    if (dest.rdbuf()->sputn(d, len) != len) {
      dest.setstate(ios_base::badbit);
    }
  }
  return dest;
}

template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  for (int i = 0; i < (int)v.size(); i++) {
    os << v[i] << (i + 1 != (int)v.size() ? " " : "");
  }
  return os;
}

template <typename T>
ostream &operator<<(ostream &os, const set<T> &set_var) {
  for (auto itr = set_var.begin(); itr != set_var.end(); itr++) {
    os << *itr;
    ++itr;
    if (itr != set_var.end()) os << " ";
    itr--;
  }
  return os;
}

template <typename T>
ostream &operator<<(ostream &os, const unordered_set<T> &set_var) {
  for (auto itr = set_var.begin(); itr != set_var.end(); itr++) {
    os << *itr;
    ++itr;
    if (itr != set_var.end()) os << " ";
    itr--;
  }
  return os;
}

template <typename T, typename U>
ostream &operator<<(ostream &os, const map<T, U> &map_var) {
  for (auto itr = map_var.begin(); itr != map_var.end(); itr++) {
    os << itr->first << " -> " << itr->second << "\n";
  }
  return os;
}

template <typename T, typename U>
ostream &operator<<(ostream &os, const unordered_map<T, U> &map_var) {
  for (auto itr = map_var.begin(); itr != map_var.end(); itr++) {
    os << itr->first << " -> " << itr->second << "\n";
  }
  return os;
}

template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &pair_var) {
  os << pair_var.first << " " << pair_var.second;
  return os;
}

void out() { cout << '\n'; }
template <class T, class... Ts>
void out(const T &a, const Ts &...b) {
  cout << a;
  (cout << ... << (cout << ' ', b));
  cout << '\n';
}

void outf() { cout << '\n'; }
template <class T, class... Ts>
void outf(const T &a, const Ts &...b) {
  cout << fixed << setprecision(14) << a;
  (cout << ... << (cout << ' ', b));
  cout << '\n';
}

template <typename T>
istream &operator>>(istream &is, vector<T> &v) {
  for (T &in : v) is >> in;
  return is;
}

inline void in(void) { return; }
template <typename First, typename... Rest>
void in(First &first, Rest &...rest) {
  cin >> first;
  in(rest...);
  return;
}

template <typename T>
bool chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <typename T>
bool chmin(T &a, const T &b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}

vector<lint> dx8 = {1, 1, 0, -1, -1, -1, 0, 1};
vector<lint> dy8 = {0, 1, 1, 1, 0, -1, -1, -1};
vector<lint> dx4 = {1, 0, -1, 0};
vector<lint> dy4 = {0, 1, 0, -1};

#pragma endregion
#line 2 "verify/AizuOnlineJudge/graph/connectivity/GraphConstruction2235.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2235"
#line 1 "data-structure/union-find/UndoableUnionFind.hpp"

template <class S, auto op, auto e>
class UndoableUnionFind {
 private:
  struct HistoryData {
    int u, datu;
    S accu;
    int v, datv;
    S accv;
    int comp_cnt;
  };

  vector<int> data;
  vector<S> acc;
  stack<HistoryData> history;
  int cnt;
  int snap;

 public:
  UndoableUnionFind() {}
  UndoableUnionFind(int sz) {
    data.assign(sz, -1);
    cnt = sz;
    acc.resize(sz, e());
  }

  bool unite(int u, int v) {
    u = find(u), v = find(v);
    history.emplace(u, data[u], acc[u], v, data[v], acc[v], cnt);
    if (u == v) return false;
    if (data[u] > data[v]) swap(u, v);
    data[u] += data[v];
    data[v] = u;
    acc[u] = op(acc[u], acc[v]);
    cnt--;
    return true;
  }

  int find(int k) {
    while (data[k] >= 0) {
      k = data[k];
    }
    return k;
  }

  void update(int a, S x) {
    a = find(a);
    history.push({a, data[a], acc[a], -1, -1, e(), -1});
    acc[a] = op(acc[a], x);
  }

  S prod_components(int a) {
    return acc[find(a)];
  }

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

  int size(int k) { return (-data[find(k)]); }

  void undo() {
    HistoryData h = history.top();
    history.pop();
    data[h.u] = h.datu;
    acc[h.u] = h.accu;
    if (h.v != -1) {
      data[h.v] = h.datv;
      acc[h.v] = h.accv;
      cnt = h.comp_cnt;
    }
  }

  int components() {
    return cnt;
  }
};
#line 3 "graph/connectivity/OfflineDynamicConnectivityDFS.hpp"


template <class S, auto op, auto e>
struct OfflineDynamicConnectivity {
 private:
  struct Edge {
    int from, to;
  };

  struct Query {
    int com;
    int u, v;
    int start;
    int finish;
    lint val;
  };
  vector<Query> q;
  vector<S> res;
  int outq = 0;
  int n;
  vector<unordered_map<int, int>> ed;
  vector<vector<Edge>> node;
  vector<vector<pair<int, S>>> updates;
  vector<int> val_idx;
  UndoableUnionFind<S, op, e> d;
  int vertex_siz;
  int qtime;
  int Q_INF = 1e8;
  int idx = 0;

  vector<vector<Query>> outputQuery;

  void add(int a, int b, Edge &ed, int k = 0, int l = 0, int r = -1) {
    if (r < 0) r = n;
    if (r <= a || b <= l) return;
    if (a <= l && r <= b) {
      node[k].emplace_back(ed);
      return;
    }
    add(a, b, ed, 2 * k + 1, l, (l + r) / 2);
    add(a, b, ed, 2 * k + 2, (l + r) / 2, r);
  }

  void add_update(int a, int b, pair<int, S> x, int k = 0, int l = 0, int r = -1) {
    if (r < 0) r = n;
    if (r <= a || b <= l) return;
    if (a <= l && r <= b) {
      updates[k].emplace_back(x);
      return;
    }
    add_update(a, b, x, 2 * k + 1, l, (l + r) / 2);
    add_update(a, b, x, 2 * k + 2, (l + r) / 2, r);
  }

  void execute(int k = 0) {
    if (outq == 0) return;
    for (auto &ed : node[k]) {
      d.unite(ed.from, ed.to);
    }

    for (auto &p : updates[k]) {
      d.update(p.first, p.second);
    }

    if (k < n - 1) {
      execute(2 * k + 1);
      execute(2 * k + 2);
    } else if (k - (n - 1) < qtime) {
      int qidx = k - (n - 1);
      for (auto cur : outputQuery[qidx]) {
        int com = cur.com;
        int u = cur.u;
        int v = cur.v;
        if (com == 2) {
          res.emplace_back(d.same(u, v));
        } else if (com == 3) {
          res.emplace_back(d.components());
        } else if (com == 4) {
          res.emplace_back(d.size(u));
        } else if (com == 6) {
          res.emplace_back(d.prod_components(u));
        }
      }
    }
    for (int i = 0; i < int(node[k].size() + updates[k].size()); i++) {
      d.undo();
    }
  }

 public:
  OfflineDynamicConnectivity(int siz) {
    d = UndoableUnionFind<S, op, e>(siz);
    vertex_siz = siz;
    ed.resize(siz);
    val_idx.resize(siz, -1);
  }

  void link(int u, int v) {
    if (u > v) swap(u, v);
    if (ed[u].find(v) != ed[u].end()) return;
    qtime++;
    q.push_back({0, u, v, qtime, Q_INF, 0});
    ed[u][v] = idx;
    idx++;
  }

  void cut(int u, int v) {
    if (u > v) swap(u, v);
    qtime++;
    q.push_back({1, u, v, qtime, -1, 0});
    int pos = ed[u][v];
    q[pos].finish = qtime;
    ed[u].erase(v);
    idx++;
  }

  void update(int u, lint x) {
    qtime++;
    q.push_back({5, u, -1, qtime, Q_INF, x});
    idx++;
  }

  void is_connected(int u, int v) {
    if (u > v) swap(u, v);
    q.push_back({2, u, v, qtime, -1, 0});
    idx++;
    outq++;
  }

  void components() {
    q.push_back({3, -1, -1, qtime, -1, 0});
    idx++;
    outq++;
  }

  void size(int u) {
    q.push_back({4, u, -1, qtime, -1, 0});
    idx++;
    outq++;
  }

  void prod(int u) {
    q.push_back({6, u, -1, qtime, -1, 0});
    idx++;
    outq++;
  }

  vector<S> build() {
    qtime++;

    int sz = qtime;
    n = 1;
    while (n < sz) n *= 2;
    node.resize(2 * n - 1);
    updates.resize(2 * n - 1);
    outputQuery.resize(qtime);
    for (int i = 0; i < q.size(); i++) {
      if (q[i].com == 0) {
        Edge ed = {q[i].u, q[i].v};
        add(q[i].start, min(q[i].finish, qtime), ed);
      } else if (q[i].com == 5) {
        add_update(q[i].start, q[i].finish, {q[i].u, q[i].val});
      } else if (q[i].com != 1) {
        outputQuery[q[i].start].emplace_back(q[i]);
      }
    }
    execute();
    return res;
  }
};


#line 4 "verify/AizuOnlineJudge/graph/connectivity/GraphConstruction2235.test.cpp"

using S = int;

S op(S a, S b) {
  return a + b;
}

S e() {
  return 0;
}
int main() {
  cin.tie(0)->sync_with_stdio(0);
  int n, q;
  in(n, q);
  OfflineDynamicConnectivity<S, op, e> g(n);

  rep(i, q) {
    int com, u, v;
    in(com, u, v);
    if (com == 1) {
      g.link(u, v);
    } else if (com == 2) {
      g.cut(u, v);
    } else if (com == 3) {
      g.is_connected(u, v);
    }
  }

  for (auto x : g.build()) {
    out(x ? "YES" : "NO");
  }
}
Back to top page