제출 #911446

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
911446		NK_	Joker (BOI20_joker)	C++17	0 / 100	75 ms	30784 KiB

Joker

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define pb push_back

template<class T> using V = vector<T>;
using vi = V<int>;

struct DSU {
	vi e, p; V<array<int, 7>> ed;void init(int N) { e = vi(N, -1); p = vi(N, 0); }
	int get(int x) { return e[x] < 0 ? x : get(e[x]); }
	int parity(int x) { return e[x] < 0 ? 0 : p[x] ^ parity(e[x]); }
	bool unite(int x, int y, int t) {
		int rx = get(x), ry = get(y);
		int px = parity(x), py = parity(y);
		// cout << x << " " << y << " " << t << endl;
		// cout << rx << " " << rx << " --> " << px << " " << py << endl;

		if (rx == ry) {
			if (px == py) return 0;
			ed.pb({-1, -1, -1, -1, -1, -1}); return 1;
		}

		if (e[rx] > e[ry]) swap(rx, ry);

		ed.pb({rx, ry, e[rx], e[ry], p[rx], p[ry], t});
		e[rx] += e[ry]; e[ry] = rx; p[ry] = px ^ py ^ 1; return 1;
	}

	bool rollback(int T) {
		if (size(ed) == 0) return 0;
		auto [rx, ry, erx, ery, prx, pry, t] = ed.back(); 
		if (t < T) return 0;
		
		ed.pop_back();

		if (rx == -1) return 1;

		e[rx] = erx, p[rx] = prx;
		e[ry] = ery, p[ry] = pry;
		return 1;
	}
};


int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N, M, Q; cin >> N >> M >> Q;

	V<array<int, 2>> E(M); for(auto& x : E) { cin >> x[0] >> x[1]; --x[0], --x[1]; }


	vi lst(M); // lst r where when [l, r] is removed the graph is bipartite

	DSU D; D.init(N);

	int T = 0;
	function<void(int, int, int, int)> dnc = [&](int l, int r, int lx, int rx) {
		if (l > r) return;

		int mid = (l + r) / 2;
		
		// compute lst_mid

		++T;
		bool ok = 1;
		// cout << "HELLO" << endl;
		for(int i = l; i < mid; i++) {
			ok &= D.unite(E[i][0], E[i][1], T);
			// cout << ok << endl;
			if (!ok) break;
		}


		// cout << "START " << ok << endl;
		// for(auto e : D.ed) {
		// 	cout << e[0] << " <-> " << e[1] << endl;
		// }

		if (!ok) lst[mid] = rx;
		else {
			lst[mid] = rx - 1; 
			while(D.unite(E[lst[mid]][0], E[lst[mid]][1], T)) lst[mid]--;
		}

		// cout << "MID" << endl;
		// for(auto e : D.ed) {
		// 	cout << e[0] << " <-> " << e[1] << endl;
		// }

		while(D.rollback(T));
		--T;

		// cout << l << " " << mid << " " << r << " " << lst[mid] << endl;
		// cout << lx << " " << rx << endl;

		// for(auto e : D.ed) {
			// cout << e[0] << " <-> " << e[1] << endl;
		// }

		// cout << "DONE" << endl;

		// [l, mid - 1]

		++T;
		for(int i = rx - 1; i > lst[mid]; i--) D.unite(E[i][0], E[i][1], T);
		dnc(l, mid - 1, lx, lst[mid] + 1);

		while(D.rollback(T));
		--T;

		// [mid + 1, r]
		++T;
		
		ok = 1;
		for(int i = l; i <= mid; i++) ok &= D.unite(E[i][0], E[i][1], T);
		
		if (ok) dnc(mid + 1, r, max(mid + 1, lst[mid]), rx);
		else for(int i = mid + 1; i <= r; i++) lst[i] = rx;

		while(D.rollback(T));
		--T;
	};	

	dnc(0, M - 1, 0, M);

	// for(int i = 0; i < M; i++) {
		// lst[i] = max(lst[i], lst[i-1]);
		// cout << i << " => " << lst[i] << nl;
	// }

	for(int i = 0; i < Q; i++) {
		int l, r; cin >> l >> r; --l, --r;
		cout << (lst[l] <= r ? "NO" : "YES") << nl;
	}

	exit(0-0);
}
	

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