Submission #764562

#	Time	Username	Problem	Language	Result	Execution time	Memory
764562		MetalPower	Joker (BOI20_joker)	C++14	100 / 100	284 ms	18152 KiB

Joker

#include <bits/stdc++.h>
using namespace std;

#define pii pair<int, int>
#define fi first
#define se second

const int MX = 2e5 + 10;

// Let dp[l] be the maximum index such that removing [l, dp[l]) doesn't make the graph bipartite
// Observe that dp[i] <= dp[i + 1] <= dp[i + 2]
// Hence we can do a dnc-esque solution

// also to make the complexity much lower, we can do the 2-pointer cost usually used for dp-dnc

struct dsu{
	int p[MX << 1], sz[MX << 1];
	vector<pii> operations;

	void init(){
		for(int i = 0; i < (MX << 1); i++) p[i] = i, sz[i] = 1;
	}

	int f(int x){
		if(p[x] == x) return x;
		else return f(p[x]);
	}

	int Join(int u, int v){
		int fu = f(u), fv = f(v);
		if(fu == fv) return 0;
		if(sz[fu] < sz[fv]){
			operations.push_back({p[fu], fu});
			p[fu] = fv;
			operations.push_back({sz[fv], fv});
			sz[fv] += sz[fu];
		}else{
			operations.push_back({p[fv], fv});
			p[fv] = fu;
			operations.push_back({sz[fu], fu});
			sz[fu] += sz[fv];
		}
		return 1;
	}

	void rev(int x){
		for(int i = 0; i < x; i++){
			{
				pii bk = operations.back();
				sz[bk.se] = bk.fi;
				operations.pop_back();
			}
			{
				pii bk = operations.back();
				p[bk.se] = bk.fi;
				operations.pop_back();
			}
		}
	}

	bool con(int x){
		return f(x * 2) == f(x * 2 + 1);
	}
} D;

int N, M, Q;
vector<pii> edges;
int lf = 0, rg = -1, dp[MX];

void solve(int l, int r, int optl, int optr){

	if(r < l) return;
	// cout << "solve " << l << " " << r << '\n';

	bool is_bipartite = true;
	int op = 0;
	int mid = l + r >> 1;
	for(int i = l; i < mid; i++){
		op += D.Join(edges[i].fi * 2, edges[i].se * 2 + 1);
		op += D.Join(edges[i].fi * 2 + 1, edges[i].se * 2);
		if(D.con(edges[i].fi) || D.con(edges[i].se)){
			dp[mid] = M; is_bipartite = false;
			D.rev(op); op = 0;
			break;
		} 
	}

	if(is_bipartite){

		dp[mid] = min(mid, optl);
		for(int i = optr; i >= optl && i >= mid; i--){
			op += D.Join(edges[i].fi * 2, edges[i].se * 2 + 1);
			op += D.Join(edges[i].fi * 2 + 1, edges[i].se * 2);
			if(D.con(edges[i].fi) || D.con(edges[i].se)){
				dp[mid] = i;
				D.rev(op); op = 0;
				break;
			}
		}

		for(int i = l; i <= mid; i++){
			op += D.Join(edges[i].fi * 2, edges[i].se * 2 + 1);
			op += D.Join(edges[i].fi * 2 + 1, edges[i].se * 2);
			if(D.con(edges[i].fi) || D.con(edges[i].se)){
				is_bipartite = false;
				D.rev(op); op = 0;
				break;
			}
		}

		if(is_bipartite){
			solve(mid + 1, r, dp[mid], optr);
			D.rev(op); op = 0;
		}else{
			for(int i = mid + 1; i <= r; i++) dp[i] = M;
		}

	} else {
		for(int i = mid + 1; i <= r; i++) dp[i] = M;
	}

	for(int i = optr; i > dp[mid]; i--){
		op += D.Join(edges[i].fi * 2, edges[i].se * 2 + 1);
		op += D.Join(edges[i].fi * 2 + 1, edges[i].se * 2);
	}

	solve(l, mid - 1, optl, dp[mid]);
	D.rev(op); op = 0;
}

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

	cin >> N >> M >> Q;
	for(int i = 0; i < M; i++){
		int u, v; cin >> u >> v;
		edges.push_back({u, v});
	}
	edges.push_back({N + 1, N + 2});

	D.init();
	solve(0, M - 1, 0, M);

	for(int i =  0; i < Q; i++){
		int l, r; cin >> l >> r; l--, r--;
		if(r < dp[l]) cout << "YES\n";
		else cout << "NO\n";
	}
}

Compilation message (stderr)

Joker.cpp: In function 'void solve(int, int, int, int)':
Joker.cpp:77:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   77 |  int mid = l + r >> 1;
      |            ~~^~~

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