Submission #291899

#	Time	Username	Problem	Language	Result	Execution time	Memory
291899		Berted	Joker (BOI20_joker)	C++14	100 / 100	405 ms	18668 KiB

Joker

#include <iostream>
#include <vector>
#include <algorithm>
#include <assert.h>
#define vi vector<int>
#define pii pair<int, int>
#define fst first
#define vpi vector<pii>
#define ppi pair<pii, int>
#define snd second

using namespace std;

/*
	Idea : 
	Define R_i as the right-most index such that Query(i .. R[i]) = "YES"
	Observe that R[i - 1] <= R[i] for all i
	Therefore, we can do DnC
	:D 
*/

int n, m, q;

pii edge[200001];
int ans[200001], sz[200001];
pair<int, bool> par[200001];

pair<int, bool> fn(int u)
{
	if (u == par[u].fst) return par[u];
	else
	{
		pair<int, bool> ret = fn(par[u].fst);
		ret.snd ^= par[u].snd;
		return ret;
	}
}

inline bool jn(int a, int b, vpi& rb)
{
	pair<int, bool> parA = fn(a), parB = fn(b);
	// cout << "JOIN " << a << " - " << b << " " << parA.snd << " " << parB.snd << " , " << parA.fst << " - " << parB.fst << "\n";
	if (parA.fst != parB.fst)
	{
		if (sz[parA.fst] < sz[parB.fst]) {swap(parA, parB);}
		rb.push_back({parB.fst, sz[parB.fst]});
		sz[parA.fst] += sz[parB.fst];
		par[parB.fst] = {parA.fst, parA.snd == parB.snd};
		return 1;
	}
	return parA.snd != parB.snd;
}

inline void rollbackOp(vpi& rb)
{
	for (int i = rb.size() - 1; i >= 0; i--)
	{
		sz[par[rb[i].fst].fst] -= rb[i].snd;
		par[rb[i].fst] = {rb[i].fst, 0};
	}
	rb.clear();
}

void solve(int L, int R, int lb, int ub)
{
	if (L <= R)
	{
		int M = L + R >> 1; int early = ub + 1; vpi rbVec;
		// cout << "SOLVE " << L << " " << R << " " << M << " " << lb << " " << ub << "\n";
		for (int i = L; i < M; i++)
		{
			if (jn(edge[i].fst, edge[i].snd, rbVec) == 0) {early = i; break;}
		}
		if (early > ub)
		{
			for (int i = ub; i >= max(M, lb); i--)
			{
				if (jn(edge[i].fst, edge[i].snd, rbVec) == 0) {early = i; break;}
			}
		}
		rollbackOp(rbVec);
		if (early < M)
		{
			for (int i = early + 1; i <= R; i++) 
			{
				ans[i] = m;
				// cout << i << " -> " << ans[i] << "\n";
			}
			solve(L, early, lb, ub);
		}
		else if (early > ub)
		{
			for (int i = L; i <= R; i++) {ans[i] = i - 1;}
		}
		else
		{
			ans[M] = early - 1;
			// cout << M << " -> " << ans[M] << "\n";

			for (int i = ub; i > early; i--) {jn(edge[i].fst, edge[i].snd, rbVec);}
			solve(L, M - 1, lb, early);
			rollbackOp(rbVec);

			bool b = 1;
			for (int i = L; i <= M; i++) {b &= jn(edge[i].fst, edge[i].snd, rbVec);}
			if (b) solve(M + 1, R, early, ub);
			else for (int i = M + 1; i <= R; i++) {ans[i] = m;}
			rollbackOp(rbVec);
		}	
	}
}

int main()
{
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m >> q;
	for (int i = 0; i < n; i++) {par[i] = {i, 0}; sz[i] = 1;}
	for (int i = 0; i < m; i++)
	{
		int u, v; cin >> u >> v;
		edge[i] = {u - 1, v - 1};
	}
	solve(0, m - 1, 0, m - 1);
	for (int i = 0; i < q; i++)
	{
		int l, r; cin >> l >> r; l--; r--;
		if (r > ans[l]) {cout << "NO\n";}
		else {cout << "YES\n";}
	}
	return 0;
}

Compilation message (stderr)

Joker.cpp: In function 'void solve(int, int, int, int)':
Joker.cpp:68:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |   int M = L + R >> 1; int early = ub + 1; vpi rbVec;
      |           ~~^~~

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