Submission #810472

#	Time	Username	Problem	Language	Result	Execution time	Memory
810472		ymm	Joker (BOI20_joker)	C++17	100 / 100	212 ms	13756 KiB

Joker

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
typedef std::pair<int,int> pii;
typedef long long ll;
using namespace std;

const int N = 200'010;

namespace dsu {
	int par[N];
	int sz[N];
	bool parpar[N];

	void init() { fill(par, par+N, -1); fill(sz, sz+N, 1); }
	pii rt(int v) {
		int p = 0;
		while (par[v] != -1) {
			p ^= parpar[v];
			v = par[v];
		}
		return {v, p};
	}
	bool can(int v, int u) {
		auto [x1, y1] = rt(v);
		auto [x2, y2] = rt(u);
		return x1 != x2 || y1 != y2;
	}
	vector<pii> his;
	bool unite(int v, int u) {
		auto [x1, y1] = rt(v);
		auto [x2, y2] = rt(u);
		if (x1 == x2) {
			if (y1 == y2)
				return 0;
			his.push_back({-1, -1});
			return 1;
		}
		if (sz[x1] < sz[x2]) {
			swap(x1, x2);
			swap(y1, y2);
		}
		par[x2] = x1;
		parpar[x2] = 1 ^ y1 ^ y2;
		sz[x1] += sz[x2];
		his.emplace_back(x1, x2);
		return 1;
	}
	void undo() {
		auto [x1, x2] = his.back();
		his.pop_back();
		if (x2 == -1)
			return;
		sz[x1] -= sz[x2];
		par[x2] = -1;
	}
}

pii E[N];
bool unite(int i) { return dsu::unite(E[i].first, E[i].second); }

int L, R;
vector<int> dir;

void undo() {
	dsu::undo();
	if (dir.back() == 0)
		--L;
	else
		++R;
	dir.pop_back();
}

bool mov(int l, int r)
{
	if (l > r)
		return 0;
	while (l < L)
		undo();
	while (R < r)
		undo();
	while (L < l) {
		if (!unite(L))
			return 0;
		dir.push_back(0);
		++L;
	}
	while (r < R) {
		if (!unite(R-1))
			return 0;
		dir.push_back(1);
		--R;
	}
	return 1;
}

int mn_ac[N];

void dc(int l1, int r1, int l2, int r2)
{
	if (l1 >= r1)
		return;
	//cerr << l1 << ' ' << r1 << " -> " << l2 << ' ' << r2 << '\n';
	int m = (l1 + r1)/2;
	mov(l1, r2-1);
	if (!mov(m, r2-1)) {
		Loop (i,m,r1)
			mn_ac[i] = N;
		dc(l1, m, l2, r2);
		return;
	}
	while (mov(m, R-1));
	int ans = R;
	mn_ac[m] = ans;
	//cerr << "mn[" << m << "] = " << ans << '\n';
	dc(l1, m, l2, ans+1);
	dc(m+1, r1, ans, r2);
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	int n, m, q;
	cin >> n >> m >> q;
	dsu::init();
	L = 0;
	R = m;
	Loop (i,0,m) {
		int v, u;
		cin >> v >> u;
		E[i] = {v, u};
	}
	dc(0, m+1, 0, m+1);
	Loop (i,0,q) {
		int l, r;
		cin >> l >> r;
		--l;
		if (r >= mn_ac[l])
		//if (mov(l, r))
			cout << "NO\n";
		else
			cout << "YES\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