Submission #1312633

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312633		vlomaczk	Joker (BOI20_joker)	C++20	0 / 100	200 ms	38300 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, g_r;
	vector<vector<pair<int, int>>> color_r;
	vector<set<int>> g;
	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, 1);
		g.resize(n+1);
	}

	int Find(int v) {
		return (rep[v]==v ? v : Find(rep[v]));
	}

	void dfs(int v, int p) {
		color_r.back().push_back({v,color[v]});
		color[v] = 1 - color[v];
		for(auto u : g[v]) if(u!=p) dfs(u,v);
	}

	void add(int i) {
		size++;
		ans_r.push_back(bipartite);
		rep_r.push_back({});
		sajz_r.push_back({});
		color_r.push_back({});
		g_r.push_back({});
		auto[a,b] = e[i];
		if(Find(a)==Find(b)) {
			if(color[a]==color[b]) {
				bipartite = 0;
			}
		} else {
			if(sajz[Find(b)] > sajz[Find(a)]) swap(a,b);
			if(color[a]==color[b]) dfs(b,b);
			g[a].insert(b);
			g[b].insert(a);
			g_r.back() = {a, b};
			a = Find(a);
			b = Find(b);
			sajz_r.back() = {a,sajz[a]};
			rep_r.back() = {b,rep[b]};
			sajz[a] += sajz[b];
			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[x,y] = g_r.back();
		g[x].erase(y); g[y].erase(x);
		g_r.pop_back();
		for(auto[k,l] : color_r.back()) color[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) 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=m; i<=r1; ++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