Submission #1265224

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265224		OgradL	Joker (BOI20_joker)	C++20	100 / 100	226 ms	18344 KiB

Joker

#include <algorithm>
#include <array>
#include <functional>
#include <iostream>
#include <vector>
using namespace std;

struct DSU{

	int N;
	vector<int> sz;
	vector<pair<int, int>> par;
	vector<array<int, 4>> history;
	int ans;

	DSU(int n){
		N = n;
		sz.assign(N, 1);
		par.resize(N);
		for (int i = 0; i < N; i++)
			par[i] = {i, 0};
		ans = 0;
	}

	pair<int, int> get_par(int x){
		if (x == par[x].first)
			return par[x];
		pair<int, int> parent = get_par(par[x].first);
		// par[x].first = parent.first;
		// par[x].second += parent.second;
		return {parent.first, parent.second + par[x].second};
	}

	int onion_set(int a, int b){
		auto A = get_par(a);
		auto B = get_par(b);

		if (A.first != B.first){
			if (sz[A.first] < sz[B.first])
				swap(A, B);

			history.push_back({B.first, A.first, par[B.first].second, ans});

			sz[A.first] += sz[B.first];
			par[B.first].first = A.first;
			par[B.first].second = B.second + 1 + A.second;

			return 0;
		}
		history.push_back({-1, -1, -1, ans});
		ans |= (A.second + B.second + 1) & 1;
		return A.second + B.second + 1;
	}

	void roll_back(int cnt = 1){
		while (cnt--){
			auto [B, A, d, pre_ans] = history.back();
			history.pop_back();
			ans = pre_ans;
			if (B == -1)
				continue;

			sz[A] -= sz[B];
			par[B].first = B;
			par[B].second = d;

		}
	}
};

int main(){

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int N, M, Q;
	cin >> N >> M >> Q;

	vector<pair<int, int>> edges;
	int a, b;
	for (int i = 0; i < M; i++){
		cin >> a >> b;
		--a, --b;

		edges.push_back({a, b});
	}

	vector<array<int, 3>> queries;
	vector<int> answers(Q);
	int l, r;
	for (int i = 0; i < Q; i++){
		cin >> l >> r;
		--l, --r;

		queries.push_back({l, r, i});
	}

	vector<int> last(M, -1);
	DSU dsu(N);

	auto add_edges = [&](int l, int r){
		int d = l < r ? 1 : -1;

		while (l != r){
			auto [a, b] = edges[l];
			dsu.onion_set(a, b);
			l += d;
		}
	};

	r = M-1;
	while (r >= 0 && !dsu.ans){
		add_edges(r, r+1);
		r--;
	}
	last[0] = r;
	dsu.roll_back(M - 1 - r);

	function<void(int, int, int, int)> rec = [&](int l1, int r1, int l2, int r2){
		if (r1 - l1 <= 1){
			return;
		}

		int mid = (l1 + r1) / 2;

		add_edges(l1, mid);

		int r = r2-1;
		while (r > l2 && !dsu.ans){
			add_edges(r, r+1);
			r--;
		}
		last[mid] = r;

		dsu.roll_back(mid - l1 + r2 - 1 - r);


		add_edges(r+1, r2);

		rec(l1, mid, l2, r+1);

		dsu.roll_back(r2 - r - 1);


		add_edges(l1, mid);

		rec(mid, r1, r, r2);

		dsu.roll_back(mid - l1);
	};
	rec(0, M, last[0], M);

	for (auto [l, r, idx] : queries){
		answers[idx] = r <= last[l];
	}

	for (int x : answers){
		if (x)
			cout << "YES\n";
		else
			cout << "NO\n";
	}

	return 0;
}

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