Submission #76911798

---

Source Code Expand

#include <bits/stdc++.h>
// #include <boost/multiprecision/cpp_int.hpp>
using namespace std;
using std::cerr, std::cin, std::cout;
#define vec vector
#if __has_include(<atcoder/all>)
#include <atcoder/all>
// using mint = atcoder::modint998244353;
using mint = atcoder::modint;
std::istream &operator>>(std::istream &is, mint &a) {
	long long t;
	is >> t;
	a = t;
	return is;
}
std::ostream &operator<<(std::ostream &os, mint a) { return os << a.val(); }
// vec<mint> operator*(const vec<mint> &a, const vec<mint> &b) { return a.empty() || b.empty() ? vec<mint>() : atcoder::convolution(a, b); }
// vec<mint> &operator*=(vec<mint> &a, const vec<mint> &b) { return a = a * b; }
#endif
typedef long double ld;
#if LONG_MAX == 2147483647L
#undef long
#define long long long
#endif
#define uint unsigned int
#define ulong unsigned long
#define overload3(a, b, c, name, ...) name
#define rep3(i, a, b) for (int i = (a); i < (b); i++)
#define rep2(i, n) rep3(i, 0, n)
#define rep1(n) rep2(__i, n)
#define rep(...) overload3(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)
#define per3(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define per2(i, n) per3(i, 0, n)
#define per1(n) per2(__i, n)
#define per(...) overload3(__VA_ARGS__, per3, per2, per1)(__VA_ARGS__)
#define all(a) a.begin(), a.end()
#define UNIQUE(a) sort(all(a)), a.erase(unique(all(a)), a.end()), a.shrink_to_fit()
#define sz(a) static_cast<int>(a.size())
#ifndef DEBUG
#define cerr \
	if (false) cerr
// #undef assert
// #define assert(...) void(0)
#undef endl
#define endl '\n'
#endif
ostream &operator<<(ostream &os, __int128_t value) {
	ostream::sentry s(os);
	if (s) {
		__uint128_t tmp = value < 0 ? -value : value;
		char buffer[128];
		char *d = std::end(buffer);
		do {
			--d;
			*d = "0123456789"[tmp % 10];
			tmp /= 10;
		} while (tmp != 0);
		if (value < 0) --d, *d = '-';
		const int len = std::end(buffer) - d;
		if (os.rdbuf()->sputn(d, len) != len) os.setstate(std::ios_base::badbit);
	}
	return os;
}
template <typename T, typename S>
ostream &operator<<(ostream &os, pair<T, S> a) {
	return os << a.first << ' ' << a.second;
};
template <typename T>
ostream &operator<<(ostream &os, vector<T> a) {
	const int n = a.size();
	rep(i, n) {
		os << a[i];
		if (i + 1 != n) os << " ";
	}
	return os;
}
template <typename T, typename S>
istream &operator>>(istream &is, pair<T, S> &a) {
	return is >> a.first >> a.second;
}
template <typename T, size_t n>
ostream &operator<<(ostream &os, array<T, n> a) {
	rep(i, n) {
		os << a[i];
		if (i + 1 != n) os << " ";
	}
	return os;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &a) {
	for (T &i : a) is >> i;
	return is;
}
template <typename T, typename S>
bool chmin(T &x, S y) {
	if ((T)y < x) {
		x = (T)y;
		return true;
	}
	return false;
}
template <typename T, typename S>
bool chmax(T &x, S y) {
	if (x < (T)y) {
		x = (T)y;
		return true;
	}
	return false;
}
template <typename T>
void operator++(vector<T> &a) {
	for (T &i : a) ++i;
}
template <typename T>
void operator--(vector<T> &a) {
	for (T &i : a) --i;
}
template <typename T>
void operator++(vector<T> &a, int) {
	for (T &i : a) i++;
}
template <typename T>
void operator--(vector<T> &a, int) {
	for (T &i : a) i--;
}
void init(), solve();
int main() {
	// srand((unsigned)time(NULL));
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(20);
	cerr << fixed << setprecision(20);
	init();
	int t = 1;
	// cin >> t;
	while (t--) solve();
}
void init() {
}

template <class Abel>
struct UndoUnionFind {
	vector<int> par;
	vector<int> rank;
	vector<Abel> diff_weight;
	Abel SUM_UNITY;

	struct History {
		bool merged;
		int x, y;
		int rank_x;
		int par_y;
		Abel diff_y;
	};

	vector<History> hist;

	UndoUnionFind(int n = 1, Abel SUM_UNITY = 0) {
		init(n, SUM_UNITY);
	}

	void init(int n = 1, Abel SUM_UNITY_ = 0) {
		SUM_UNITY = SUM_UNITY_;
		par.resize(n);
		rank.resize(n);
		diff_weight.resize(n);
		hist.clear();
		for (int i = 0; i < n; ++i) {
			par[i] = i;
			rank[i] = 0;
			diff_weight[i] = SUM_UNITY;
		}
	}

	int root(int x) const {
		while (par[x] != x) x = par[x];
		return x;
	}

	Abel weight(int x) const {
		Abel res = SUM_UNITY;
		while (par[x] != x) {
			res += diff_weight[x];
			x = par[x];
		}
		return res;
	}

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

	bool merge(int x, int y, Abel w) {
		w += weight(x);
		w -= weight(y);

		x = root(x);
		y = root(y);

		if (x == y) {
			hist.push_back({false, -1, -1, -1, -1, SUM_UNITY});
			return false;
		}

		if (rank[x] < rank[y]) {
			swap(x, y);
			w = -w;
		}

		hist.push_back({true, x, y, rank[x], par[y], diff_weight[y]});

		if (rank[x] == rank[y]) ++rank[x];

		par[y] = x;
		diff_weight[y] = w;

		return true;
	}

	Abel diff(int x, int y) const {
		return weight(y) - weight(x);
	}

	void undo() {
		History h = hist.back();
		hist.pop_back();

		if (!h.merged) return;

		rank[h.x] = h.rank_x;
		par[h.y] = h.par_y;
		diff_weight[h.y] = h.diff_y;
	}
};
struct S {
	int ty;
	int l, r;
	mint x;
};
void solve() {
	int n, q;
	long k;
	cin >> n >> k >> q;
	mint::set_mod(k);
	vec<S> a(q + 1);
	a[0] = {-1, -1, -1, -1};
	vec<string> ans(q);
	vec<vec<int>> g(q + 1);
	rep(i, 1, q + 1) {
		int ty, b, l, r;
		cin >> ty >> b >> l >> r;
		l--;
		g[b].push_back(i);
		mint x = 0;
		if (ty == 0) cin >> x;
		a[i] = {ty, l, r, x};
	}
	UndoUnionFind<mint> uf(n + 1);
	auto f = [&](auto f, int idx) -> void {
		const auto [ty, l, r, x] = a[idx];
		bool undo = false;
		if (ty == 0) {
			if (uf.issame(l, r) && uf.diff(l, r) != x) ans[idx - 1] = "NO";
			else {
				ans[idx - 1] = "YES";
				uf.merge(l, r, x);
				undo = true;
			}
		}
		if (ty == 1) {
			if (uf.issame(l, r)) ans[idx - 1] = to_string(uf.diff(l, r).val());
			else ans[idx - 1] = "UNKNOWN";
		}
		for (int idxx : g[idx]) f(f, idxx);
		if (undo) uf.undo();
	};
	f(f, 0);
	for (string s : ans) cout << s << endl;
}

Submission Info

Judge Result