Test/PersistentUnionFind.test.cpp

View this file on GitHub
Last update: 2021-03-18 15:32:11+09:00
Problem: https://judge.yosupo.jp/problem/persistent_unionfind

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/persistent_unionfind"

#include "DataStructure/PersistentUnionFind.hpp"

#include <cstdio>
#include <vector>

int main() {
	int N, Q;
	scanf("%d %d", &N, &Q);
	
	using PUF = PersistentUnionFind<6>;
	std::vector<PUF> hist(Q + 1);
	
	for (int i = 0; i < Q; ++i) {
		int t, k, u, v;
		scanf("%d %d %d %d", &t, &k, &u, &v);
		++k;
		if (t == 0) hist[i + 1] = (hist[k].unite(u, v));
		else printf("%d\n", hist[k].issame(u, v));
	}
}

#line 1 "Test/PersistentUnionFind.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/persistent_unionfind"

#line 1 "DataStructure/PersistentUnionFind.hpp"



#line 1 "DataStructure/PersistentArray.hpp"



#include <memory>
#include <utility>

/**
 * @brief https://tkmst201.github.io/Library/DataStructure/PersistentArray.hpp
 */
template<typename T, int M>
struct PersistentArray {
	static_assert(M > 1);
	
	using value_type = T;
	using const_reference = const value_type &;
	using size_type = std::size_t;
	
private:
	struct Node;
	using sptr_type = std::shared_ptr<Node>;
	using node_ptr = Node *;
	using const_ptr = const Node *;
	struct Node {
		sptr_type childs[M];
		value_type val;
		Node(const_reference val) : val(val) {}
	};
	
private:
	sptr_type root;
	value_type def_val;
	
private:
	PersistentArray(const sptr_type & root, const_reference def_val) : root(root), def_val(def_val) {}
	
public:
	explicit PersistentArray(const_reference def_val = 0) : root(nullptr), def_val(def_val) {}
	
	PersistentArray set(size_type k, const_reference x) const {
		const_ptr node = root.get();
		sptr_type new_root = std::make_shared<Node>(k == 0 ? x : (node ? node->val : def_val));
		node_ptr new_node = new_root.get();
		for (; k > 0; k /= M) {
			const size_type m = k % M;
			if (node) {
				for (size_type i = 0; i < M; ++i) if (i != m) new_node->childs[i] = node->childs[i];
				new_node->childs[m] = std::make_shared<Node>(k < M ? x : (node->childs[m] ? node->childs[m]->val : def_val));
				node = node->childs[m].get();
			}
			else new_node->childs[m] = std::make_shared<Node>(k < M ? x : def_val);
			new_node = new_node->childs[m].get();
		}
		if (node) for (size_type i = 0; i < M; ++i) new_node->childs[i] = node->childs[i];
		return {std::move(new_root), def_val};
	}
	
	void destructive_set(size_type k, const_reference x) {
		if (!root) root = std::make_shared<Node>(k == 0 ? x : def_val);
		node_ptr node = root.get();
		for (; k >= M; k /= M) {
			const size_type m = k % M;
			if (!node->childs[m]) node->childs[m] = std::make_shared<Node>(def_val);
			node = node->childs[m].get();
		}
		if (node->childs[k]) node->childs[k]->val = x;
		else node->childs[k] = std::make_shared<Node>(x);
	}
	
	const_reference get(size_type k) const noexcept {
		const_ptr node = root.get();
		while (k > 0 && node) {
			node = node->childs[k % M].get();
			k /= M;
		}
		return k == 0 && node ? node->val : def_val;
	}
};


#line 5 "DataStructure/PersistentUnionFind.hpp"

#include <cstdint>
#line 8 "DataStructure/PersistentUnionFind.hpp"

/**
 * @brief https://tkmst201.github.io/Library/DataStructure/PersistentUnionFind.hpp
 */
template<int M>
struct PersistentUnionFind {
	static_assert(M > 1);
	
	using size_type = std::size_t;
	
private:
	using parray_type = PersistentArray<int, M>;
	parray_type dat;
	
public:
	PersistentUnionFind() : dat(-1) {}
	
private:
	PersistentUnionFind(const parray_type & dat) : dat(dat) {}
	
public:
	size_type find(size_type x) const noexcept {
		return find_sub(x).first;
	}
	
	size_type size(size_type x) const noexcept {
		return find_sub(x).second;
	}
	
private:
	std::pair<size_type, int> find_sub(size_type x) const noexcept {
		int d;
		for (d = dat.get(x); d >= 0; d = dat.get(x)) x = d;
		return {x, -d};
	}
	
public:
	PersistentUnionFind unite(size_type x, size_type y) const {
		if (x == y) return *this;
		auto px = find_sub(x), py = find_sub(y);
		if (px.first == py.first) return *this;
		if (px.second > py.second) std::swap(px, py);
		return dat.set(px.first, py.first).set(py.first, -(px.second + py.second));
	}
	
	void destructive_unite(size_type x, size_type y) {
		if (x == y) return;
		auto px = find_sub(x), py = find_sub(y);
		if (px.first == py.first) return;
		if (px.second > py.second) std::swap(px, py);
		dat.destructive_set(px.first, py.first);
		dat.destructive_set(py.first, -(px.second + py.second));
	}
	
	bool issame(size_type x, size_type y) const noexcept {
		return x == y ? true : find(x) == find(y);
	}
};


#line 4 "Test/PersistentUnionFind.test.cpp"

#include <cstdio>
#include <vector>

int main() {
	int N, Q;
	scanf("%d %d", &N, &Q);
	
	using PUF = PersistentUnionFind<6>;
	std::vector<PUF> hist(Q + 1);
	
	for (int i = 0; i < Q; ++i) {
		int t, k, u, v;
		scanf("%d %d %d %d", &t, &k, &u, &v);
		++k;
		if (t == 0) hist[i + 1] = (hist[k].unite(u, v));
		else printf("%d\n", hist[k].issame(u, v));
	}
}