Submission #2092920

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <array>
#include <cstdint>
#include <climits>
#include <functional>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stack>
#include <stdlib.h>
#include <string>
#include <time.h>
#include <utility>
#include <vector>

using int32 = std::int_fast32_t;
using int64 = std::int_fast64_t;
using uint32 = std::uint_fast32_t;
using uint64 = std::uint_fast64_t;

class partially_persistent_disjoint_set {
	std::vector<std::pair<std::uint_fast32_t, std::uint_fast32_t>> tree;
	std::uint_fast32_t count;
public:
	partially_persistent_disjoint_set(const std::uint_fast32_t size) :tree(size, { 1,std::numeric_limits<std::uint_fast32_t>::max() }), count(0) {}
	std::uint_fast32_t find(std::uint_fast32_t ver, std::uint_fast32_t x) {
		while (tree[x].second <= ver) {
			x = tree[x].first;
		}
		return x;
	}
	std::uint_fast32_t unite(std::uint_fast32_t x, std::uint_fast32_t y) {
		++count;
		x = find(count, x);
		y = find(count, y);
		if (x == y) return count;
		if (tree[x].first < tree[y].first) std::swap(x, y);
		tree[x].first += tree[y].first;
		tree[y] = { x,count };
		return count;
	}
	bool same(std::uint_fast32_t ver, std::uint_fast32_t x, std::uint_fast32_t y) {
		return find(ver, x) == find(ver, y);
	}
};

int main(void) {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	uint32 n, m;
	std::cin >> n >> m;
	partially_persistent_disjoint_set S(n);
	uint32 a, b;
	for (uint32 i = 0;i < m;++i) {
		std::cin >> a >> b;
		--a;--b;
		S.unite(a, b);
	}
	uint32 q;
	std::cin >> q;
	uint32 x, y;
	do {
		std::cin >> x >> y;
		--x;--y;
		uint32 ng = 0, ok = m + 1;
		while (ok - ng > 1) {
			uint32 mid = (ng + ok) / 2;
			if (S.same(mid, x, y)) {
				ok = mid;
			}
			else {
				ng = mid;
			}
		}
		if (ng == m) std::cout << "-1\n";
		else std::cout << ok << "\n";
	} while (--q);
	return 0;
}

Submission Info

Judge Result