Submission #1034564

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034564		dutinmeow	Joker (BOI20_joker)	C++17	100 / 100	884 ms	27704 KiB

Joker

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include <bits/stdc++.h>

namespace std {

template<class Fun>
class y_combinator_result {
	Fun fun_;
public:
	template<class T>
	explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}

	template<class ...Args>
	decltype(auto) operator()(Args &&...args) {
		return fun_(std::ref(*this), std::forward<Args>(args)...);
	}
};

template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
	return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

} // namespace std

struct rollback_union_find {
	std::vector<int> par;
	std::stack<std::pair<int, int>> stk;

	rollback_union_find(int n) {
		par.resize(n);
		iota(par.begin(), par.end(), 0);
	}

	int leader(int u) {
		if (u == par[u])
			return u;
		stk.emplace(u, par[u]);
		return par[u] = leader(par[u]);
	}

	void merge(int u, int v) {
		u = leader(u), v = leader(v);
		if (u == v)
			return;
		stk.emplace(v, v);
		par[v] = u;
	}

	bool same(int u, int v) { return leader(u) == leader(v); }

	int version() { return (int)stk.size(); }

	void rollback(int ver) {
		while ((int)stk.size() > ver) {
			par[stk.top().first] = stk.top().second;
			stk.pop();
		}
	}
};

int main() {
	using namespace std;
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int N, M, Q;
	cin >> N >> M >> Q;
	vector<pair<int, int>> E(M);
	for (auto &[u, v] : E) {
		cin >> u >> v;
		u--, v--;
	}

	int max_l = 0;
	vector<pair<int, int>> Z(Q);
	for (auto &[l, r] : Z) {
		cin >> l >> r;
		l--, r--;
		max_l = max(max_l, l);
	}

	vector<int> ans(M, -1);
	rollback_union_find dsu(2 * N);

	y_combinator([&](auto self, int ql, int qr, int al, int ar) -> void {
		if (qr < ql)
			return;
		if (al == ar) {
			for (int i = ql; i <= qr; i++)
				ans[i] = al;
			return;
		}

		int qm = (ql + qr) / 2, ver = dsu.version();
		for (int i = ql; i < qm; i++) {
			dsu.merge(E[i].first, E[i].second + N);
			dsu.merge(E[i].first + N, E[i].second);
			if (dsu.same(E[i].first, E[i].first + N) || 
				dsu.same(E[i].second, E[i].second + N)) {
				ans[qm] = M;
				break;
			}
		}
		if (ans[qm] == -1) {
			for (int i = ar; i >= al; i--) {
				if (i == M)
					continue;
				dsu.merge(E[i].first, E[i].second + N);
				dsu.merge(E[i].first + N, E[i].second);
				if (dsu.same(E[i].first, E[i].first + N) || 
					dsu.same(E[i].second, E[i].second + N)) {
					ans[qm] = i;
					break;
				}
			}
			if (ans[qm] == -1)
				ans[qm] = qm;
		}
		dsu.rollback(ver);

		bool b = false;
		for (int i = ar; i > ans[qm]; i--) {
			if (i == M)
				continue;
			dsu.merge(E[i].first, E[i].second + N);
			dsu.merge(E[i].first + N, E[i].second);
			if (dsu.same(E[i].first, E[i].first + N) || 
				dsu.same(E[i].second, E[i].second + N)) {
				b = true;
				break;
			}
		}
		if (b) {
			for (int i = ql; i <= qm; i++)
				ans[i] = ans[qm];
		} else {
			self(ql, qm - 1, al, ans[qm]);
		}
		dsu.rollback(ver);

		b = false;
		for (int i = ql; i <= qm; i++) {
			dsu.merge(E[i].first, E[i].second + N);
			dsu.merge(E[i].first + N, E[i].second);	
			if (dsu.same(E[i].first, E[i].first + N) || 
				dsu.same(E[i].second, E[i].second + N)) {
				b = true;
				break;
			}
		}
		if (b) {
			for (int i = qm + 1; i <= qr; i++)
				ans[i] = M;
		} else {
			self(qm + 1, qr, ans[qm], ar);
		}
		dsu.rollback(ver);
	})(0, max_l, 0, M);

	for (auto [l, r] : Z) 
		cout << (r < ans[l] ? "YES\n" : "NO\n");
}

• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 25 / 25
• Subtask 4: 10 / 10
• Subtask 5: 22 / 22
• Subtask 6: 29 / 29