Submission #911458

#	Time	Username	Problem	Language	Result	Execution time	Memory
911458		NK_	Joker (BOI20_joker)	C++17	100 / 100	230 ms	22716 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>;

const int INF = 1e9;
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 ? p[x] : 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, t}); 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;
	int cur = 0; for(; cur < M; cur++) {
		if (!D.unite(E[cur][0], E[cur][1], T)) break;
	}

	while(D.rollback(T));

	for(int i = cur+1; i < M; i++) lst[i] = M;

	function<void(int, int, int, int)> dnc = [&](int l, int r, int lx, int rx) {
		int mid = (l + r) / 2;
		
		// compute lst_mid

		++T;
		for(int i = l; i < mid; i++) D.unite(E[i][0], E[i][1], T);

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

		for(int i = rx; i >= mid; i--) {
			if (!D.unite(E[i][0], E[i][1], T)) {
				lst[mid] = i;
				break;
			}
		}


		// 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]

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

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

		// [mid + 1, r]
		if (mid < r) {
			++T;

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

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

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

	// 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: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 25 / 25
• Subtask 4: 10 / 10
• Subtask 5: 22 / 22
• Subtask 6: 29 / 29