Submission #1200075

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200075		ByeWorld	Joker (BOI20_joker)	C++20	100 / 100	368 ms	8364 KiB

Joker

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
const int MAXN = 2e5+10;
const int MAXA = 250001;
using namespace std;
const int INF = 1e9;
typedef pair<int,int> pii;
typedef pair<int,pii> ipii;
 
int n;
vector<int> snapshot;
struct dsu {
	int par[MAXN], siz[MAXN], cc;
	bool off[MAXN];
	vector<array<int,4>> roll;
	void bd(){
		cc = n;
		for(int i=1; i<=n+5; i++)
			par[i] = i, siz[i] = 1;
	}
	pii f(int x){
		bool ret = 0;
		while(par[x]!=x){
			ret ^= off[x];
			x = par[x];
		}
		return pii(x, ret);
	}
	bool mer(int _x, int _y){
		pii x = f(_x), y = f(_y);
		if(x.fi==y.fi){
			roll.pb({-1,-1,-1,-1});
			if(x.se == y.se) return 0; // invalid
			return 1;
		}
		cc--;
		if(siz[x.fi] > siz[y.fi]) swap(x, y); // x->y
		roll.pb({x.fi, siz[x.fi], y.fi, siz[y.fi]});
		
		off[x.fi] = x.se^y.se^1;
		siz[y.fi] += siz[x.fi];
		par[x.fi] = y.fi; 
		return 1;
	}
	void rb(){
		if(roll.empty()){
			cout << "jnck\n"; assert(false);
		}
		auto ba = roll.back(); roll.pop_back();
		if(ba[0] == -1) return;
 
		cc++;
		siz[ba[2]] = ba[3];
		siz[ba[0]] = ba[1];
		par[ba[0]] = ba[0];
	}
	void until(int x){
		while(roll.size() != x)
			rb();
	}
} DSU;
int m, Q, las[MAXN]; // las[l] = x, 1 - l-1, x+1 - m, bipart
int u[MAXN], v[MAXN];
bool add(int id){
	return DSU.mer(u[id], v[id]);
}
 
void DNC(int l, int r, int x, int y){ // 1-l-1, y+1,m
	if(l>r) return;
	int mid = md, siz = DSU.roll.size();
	bool bip = 1;
	for(int i=l; i<=mid-1; i++) bip &= add(i);
	int siz2 = DSU.roll.size();
// cout << bip <<' ' <<mid << ' ' <<x<<' ' <<y<<" mid\n";
 
	if(!bip){
		for(int i=mid; i<=m; i++) las[i] = y;
	} else {
		int ret = y;
		while(x <= ret){
			las[mid] = ret;
			if(!add(ret)) break;
			ret--;
		}
		// cout << " her\n";
		DSU.until(siz2);
		if(!add(mid)){
			for(int i=mid+1; i<=m; i++) las[i] = y;
		} else {
			DNC(mid+1, r, las[mid], y);
		}
	}
	DSU.until(siz);
	for(int i=y; i>=las[mid]+1; i--) add(i);
	DNC(l, mid-1, x, las[mid]);
	DSU.until(siz);
}
signed main(){
	cin>>n>>m>>Q;
	DSU.bd();
	for(int i=1; i<=m; i++)cin>>u[i]>>v[i];
	u[m+1] = n+3; v[m+1] = n+4;
	bool bi = 1;
	for(int i=1; i<=m; i++) bi &= add(i);
	if(!bi){
		DSU.until(0);
		DNC(1,m,1,m+1);
	}
	// for(int i=1; i<=m; i++)
	// 	cout << i << ' ' << las[i] << " las\n";
	while(Q--){	
		int l, r; cin>>l>>r;
		cout << (las[l] <= r ? "NO\n" : "YES\n");
	}
}

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