test/datastructure/disjoint_set_union_with_potential/aoj_dsl_1_b.test.cpp

• View this file on GitHub
• Last update: 2024-10-03 01:42:31+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/all/DSL_1_B

Depends on

• ポテンシャル付き Disjoint Set Union (ポテンシャル付き Union-Find) (src/datastructure/disjoint_set_union_with_potential.hpp)

Code

// verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/all/DSL_1_B

#include "src/datastructure/disjoint_set_union_with_potential.hpp"

#include <iostream>

using namespace std;

int main() {
	int n, q;
	cin >> n >> q;
	DisjointSetUnionWithPotential<int> dsu(n);
	while (q--) {
		int f;
		cin >> f;
		if (f == 0) {
			int x, y, z;
			cin >> x >> y >> z;
			dsu.unite(x, y, z);
		} else {
			int x, y;
			cin >> x >> y;
			if (dsu.same(x, y)) cout << dsu.difference(x, y) << endl;
			else cout << '?' << endl;
		}
	}

	return 0;
}

#line 1 "test/datastructure/disjoint_set_union_with_potential/aoj_dsl_1_b.test.cpp"
// verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/all/DSL_1_B

#line 1 "src/datastructure/disjoint_set_union_with_potential.hpp"



#include <numeric>
#include <utility>
#include <vector>

template<class T>
class DisjointSetUnionWithPotential {
private:
	std::vector<int> rank, size, p;
	std::vector<T> pot;
	int num{};

public:
	DisjointSetUnionWithPotential(int n) : rank(n), size(n, 1), p(n), pot(n), num(n) {
		std::iota(p.begin(), p.end(), 0);
	}

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

	// potential(y) = potential(x) + d
	bool unite(int x, int y, T d) {
		d += potential(x);
		d -= potential(y);
		x = root(x);
		y = root(y);
		if (x == y) return d == 0;
		--num;
		if (rank[x] < rank[y]) {
			std::swap(x, y);
			d = -d;
		}
		if (rank[x] == rank[y]) ++rank[x];
		p[y] = x;
		pot[y] = d;
		size[x] += size[y];
		return true;
	}

	int root(int x) {
		if (p[x] == x) return x;
		int r = root(p[x]);
		pot[x] += pot[p[x]];
		return p[x] = r;
	}

	T potential(int x) {
		root(x);
		return pot[x];
	}

	T difference(int x, int y) { return potential(y) - potential(x); }

	int get_size(int x) { return size[root(x)]; }

	[[nodiscard]] int forest_size() const { return num; }
};


#line 4 "test/datastructure/disjoint_set_union_with_potential/aoj_dsl_1_b.test.cpp"

#include <iostream>

using namespace std;

int main() {
	int n, q;
	cin >> n >> q;
	DisjointSetUnionWithPotential<int> dsu(n);
	while (q--) {
		int f;
		cin >> f;
		if (f == 0) {
			int x, y, z;
			cin >> x >> y >> z;
			dsu.unite(x, y, z);
		} else {
			int x, y;
			cin >> x >> y;
			if (dsu.same(x, y)) cout << dsu.difference(x, y) << endl;
			else cout << '?' << endl;
		}
	}

	return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_sample_00.in	AC	13 ms	7 MB
g++	01_small_00.in	AC	13 ms	7 MB
g++	02_corner_00.in	AC	12 ms	7 MB
g++	03_general_00.in	AC	13 ms	7 MB
g++	04_rand_00.in	AC	12 ms	7 MB
g++	04_rand_01.in	AC	13 ms	7 MB
g++	04_rand_02.in	AC	12 ms	7 MB
g++	04_rand_03.in	AC	12 ms	7 MB
g++	04_rand_04.in	AC	12 ms	7 MB
g++	04_rand_05.in	AC	13 ms	7 MB
g++	04_rand_06.in	AC	13 ms	7 MB
g++	04_rand_07.in	AC	13 ms	7 MB
g++	05_large_00.in	AC	92 ms	9 MB
g++	05_large_01.in	AC	74 ms	7 MB
g++	06_maximum_00.in	AC	136 ms	9 MB
g++	06_maximum_02.in	AC	157 ms	9 MB
g++	07_dense_00.in	AC	22 ms	7 MB
g++	07_dense_01.in	AC	33 ms	7 MB
g++	07_dense_02.in	AC	63 ms	7 MB
g++	07_dense_03.in	AC	108 ms	9 MB
g++	08_shell_00.in	AC	256 ms	9 MB
g++	09_extreme_line_00.in	AC	242 ms	9 MB
g++	09_extreme_same_00.in	AC	264 ms	9 MB
g++	09_extreme_same_01.in	AC	276 ms	9 MB
clang++	00_sample_00.in	AC	12 ms	15 MB
clang++	01_small_00.in	AC	11 ms	15 MB
clang++	02_corner_00.in	AC	11 ms	9 MB
clang++	03_general_00.in	AC	11 ms	9 MB
clang++	04_rand_00.in	AC	11 ms	9 MB
clang++	04_rand_01.in	AC	11 ms	13 MB
clang++	04_rand_02.in	AC	12 ms	9 MB
clang++	04_rand_03.in	AC	11 ms	7 MB
clang++	04_rand_04.in	AC	12 ms	13 MB
clang++	04_rand_05.in	AC	12 ms	15 MB
clang++	04_rand_06.in	AC	12 ms	9 MB
clang++	04_rand_07.in	AC	12 ms	9 MB
clang++	05_large_00.in	AC	89 ms	13 MB
clang++	05_large_01.in	AC	114 ms	13 MB
clang++	06_maximum_00.in	AC	141 ms	9 MB
clang++	06_maximum_02.in	AC	174 ms	11 MB
clang++	07_dense_00.in	AC	28 ms	11 MB
clang++	07_dense_01.in	AC	47 ms	9 MB
clang++	07_dense_02.in	AC	68 ms	12 MB
clang++	07_dense_03.in	AC	168 ms	15 MB
clang++	08_shell_00.in	AC	299 ms	11 MB
clang++	09_extreme_line_00.in	AC	274 ms	11 MB
clang++	09_extreme_same_00.in	AC	303 ms	15 MB
clang++	09_extreme_same_01.in	AC	321 ms	17 MB

Back to top page