제출 #1286341

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1286341		mdobric	Joker (BOI20_joker)	C++20	100 / 100	247 ms	7360 KiB

Joker

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

const int maxn = 200005;
int n, m, q, a[maxn], b[maxn], par[maxn], vel[maxn], ans[maxn], promjena[maxn];
int tr;
vector <int> dodali;

int find (int x){
	if (par[x] == x) return x;
	return find(par[x]);
}

int boja (int x){
	if (par[x] == x) return promjena[x];
	return (boja(par[x]) + promjena[x]) % 2;
}

void add (int i){
	//cout << "dodaj " << i << endl;
	int px = find(a[i]);
	int py = find(b[i]);
	int bx = boja(a[i]);
	int by = boja(b[i]);
	if (vel[px] < vel[py]) swap(px, py);
	if (px != py){
		par[py] = px;
		vel[px] += vel[py];
		if (bx == by){
			promjena[py]++;
			promjena[py] %= 2;
		}
		//cout << "par od " << py << " je " << px << endl;
		//cout << bx << " " << by << endl;
		dodali.push_back(py);
	}
	else{
		//cout << boja(a[i]) << " " << boja(b[i]) << endl;
		if (bx == by) tr++;
		dodali.push_back(n + 1);
	}
	//for (int j = 0; j < m; j++)cout << "boja " << boja(j) << endl;
	//cout << endl;
}

void remove (int i){
	//cout << "makni " << i << endl;
	int py = dodali[dodali.size() - 1];
	if (py != n + 1){
		vel[par[py]] -= vel[py];
		par[py] = py;
		promjena[py] = 0;
		//cout << "par od " << py << " je " << py << endl;
	}
	else{
		if (boja(a[i]) == boja(b[i])) tr--;
	}
	dodali.pop_back();
}

void solve (int low, int high, int x, int y){
	//cout << low << " " << high << " " << x << " " << y << " " << tr << endl;
	if (low > high) return;
	int mid = (low + high) / 2;
	for (int i = low; i < mid; i++) add(i);
	//cout << tr << endl;
	ans[mid] = y;
	for (int i = y - 1; i >= x; i--){
		if (tr > 0) break;
		ans[mid] = i;
		add(i);
	}
	//cout << "rjesenje " << mid << " " << ans[mid] << endl;
	for (int i = ans[mid]; i < y; i++) remove(i);
	add(mid);
	solve(mid + 1, high, ans[mid], y);
	for (int i = mid; i >= low; i--) remove(i);
	for (int i = y - 1; i >= ans[mid]; i--) add(i);
	solve(low, mid - 1, x, ans[mid]);
	for (int i = ans[mid]; i < y; i++) remove(i);
}

int main (void){
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n >> m >> q;
	for (int i = 0; i < m; i++){
		cin >> a[i] >> b[i];
	}
	for (int i = 1; i <= n; i++) vel[i] = 1, par[i] = i;
	solve(0, m - 1, 0, m);
	for (int i = 0; i < q; i++){
		int l, r;
		cin >> l >> r;
		l--;
		r--;
		if (r >= ans[l]) cout << "NO" << "\n";
		else cout << "YES" << "\n";
		
	}

	return 0;
}

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