Submission #1312928

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312928		vlomaczk	Joker (BOI20_joker)	C++20	0 / 100	134 ms	18384 KiB

Joker

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

struct Bipartite {
	bool bipartite = 1;
	int m;
	vector<pair<int, int>> e;
	vector<int> rep, sajz, color;
	vector<bool> ans_r;
	vector<pair<int, int>> rep_r, sajz_r, color_r;
	int size = 0;

	int capture() { return size; } 

	Bipartite(vector<pair<int, int>> edges, int n) {
		e = edges;
		m = e.size();
		rep.assign(n+1, 0);
		for(int i=1; i<=n; ++i) rep[i] = i;
		sajz.assign(n+1, 1);
		color.assign(n+1, 0);
	}

	pair<int, int> Find(int v) {
		int c = color[v];
        while (rep[v] != v) {
            v = rep[v];
            c ^= color[v];
        }
        return {v, c};
	}

	void add(int i) {
		size++;
		ans_r.push_back(bipartite);
		rep_r.push_back({0,0});
		sajz_r.push_back({0,0});
		color_r.push_back({0,0});
		auto[a,b] = e[i];
		auto[fa,ca] = Find(a);
		auto[fb,cb] = Find(b);
		if(fa==fb) {
			if(ca==cb) {
				bipartite = 0;
			}
		} else {
			int ksor = 0;
			if(ca==cb) ksor = 1;
			a = fa;
			b = fb;
			if(sajz[b] > sajz[a]) swap(a,b);
			sajz_r.back() = {a,sajz[a]};
			rep_r.back() = {b,rep[b]};
			color_r.back() = {b, color[b]};
			sajz[a] += sajz[b];
			color[b] = ksor;
			rep[b] = a;
		}
	}

	void rollback() {
		assert(ans_r.size());
		size--;
		bipartite = ans_r.back(); ans_r.pop_back();
		auto[a,b] = rep_r.back(); rep[a] = b; rep_r.pop_back();
		auto[c,d] = sajz_r.back(); sajz[c] = d; sajz_r.pop_back();
		auto[k,l] = color_r.back(); sajz[k] = l; color_r.pop_back();
	}
};

vector<pair<int, int>> edges;
vector<int> last;

void cdq(int l1, int r1, int l2, int r2, Bipartite &bp) { // We use divide & conquer cause i < j => last[i] <= last[j]
	if(l1>r1 || l2>r2) return;
	int m = (l1+r1) / 2;
	int size1 = bp.capture();
	for(int i=l1; i<m; ++i) bp.add(i);
	last[m] = r2;
	int size2 = bp.capture();
	while(bp.bipartite && last[m] >= l2) {
		bp.add(last[m]);
		last[m]--;
	}
	while(bp.size > size2) bp.rollback();
	bp.add(m);
	cdq(m+1, r1, last[m], r2, bp);
	while(bp.size > size1) bp.rollback();
	for(int i=last[m]+1; i<=r2; ++i) bp.add(i);
	cdq(l1,m-1,l2,last[m],bp);
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int n,m,q;
	cin >> n >> m >> q;
	edges.resize(m);
	last.resize(m);
	for(int i=0; i<m; ++i) {
		cin >> edges[i].first >> edges[i].second;
	}
	Bipartite bp(edges, n);
	cdq(0,m-1,0,m-1,bp);
	while(q--) {
		int l, r;
		cin >> l >> r;
		--l; --r;
		if(r <= last[l]) cout << "YES\n";
		else cout << "NO\n";
	}

	return 0;
}

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