Submission #257263

#	Time	Username	Problem	Language	Result	Execution time	Memory
257263		maximath_1	Joker (BOI20_joker)	C++11	100 / 100	268 ms	14312 KiB

Joker

#include <stdio.h>
#include <assert.h>
#include <math.h>
#include <limits.h>
#include <time.h>
#include <algorithm>
#include <vector>
#include <random>
#include <iostream>
#include <iomanip>
#include <unordered_map>
using namespace std;

int n, m, q, lst[200005], par[200005], off[200005];

void init(){
	for(int i = 1; i <= n; i ++){
		par[i] = -1;
		off[i] = 0;
	}
}

pair<int, int> gt(int x){
	int of = 0;
	while(par[x] >= 0){
		of ^= off[x];
		x = par[x];
	}
	return {x, of};
}

vector<array<int, 4> >md;
int uni(int _x, int _y){
	pair<int, int> x = gt(_x), y = gt(_y);
	if(x.first == y.first){
		if(x.second == y.second) return 0;
		md.push_back({-1, -1, -1, -1});
		return 1;
	}

	if(par[x.first] > par[y.first]) swap(x.first, y.first);
	md.push_back({x.first, y.first, par[x.first], par[y.first]});
	par[x.first] += par[y.first];
	par[y.first] = x.first;
	off[y.first] = x.second ^ y.second ^ 1;
	return 1;
}

void rollback(){
	auto a = md.back(); md.pop_back();
	if(a[0] != -1){
		par[a[0]] = a[2];
		par[a[1]] = a[3];
	}
}

int u[200005], v[200005];
bool upd(int idx){
	if(idx == m + 1) return 1;
	return uni(u[idx], v[idx]);
}
void restore(int _sz){
	while(md.size() > _sz) rollback();
}

void dnc(int xl, int xr, int yl, int yr){
//	cout << xl << " " << xr << " " << yl << " " << yr << endl;
	if(xl > xr) return;
	int xm = (xl + xr) / 2, rs = -1, sz = md.size();
	for(int i = xl; i < xm; i ++) if(!upd(i)){
		rs = yr; assert(rs == m + 1);
		break;
	}
	int sz2 = md.size();
	if(rs == -1){
		int i = yr;
		while(i > yl && upd(i)) i --;
		rs = i;
	}

	lst[xm] = rs;
	if(lst[xm] == m + 1){
		for(int i = xm + 1; i <= xr; i ++)
			lst[i] = rs;
	}else{
		restore(sz2);
		if(!upd(xm)){
			for(int i = xm + 1; i <= xr; i ++)
				lst[i] = m + 1;
		}else
			dnc(xm + 1, xr, lst[xm], yr);
	}

	restore(sz);
	for(int i = lst[xm] + 1; i <= yr; i ++) assert(upd(i));
	dnc(xl, xm - 1, yl, lst[xm]);
	restore(sz);
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> m >> q;
	for(int i = 1; i <= m; i ++)
		cin >> u[i] >> v[i];
	
	init();
	dnc(1, m, 1, m + 1);

	for(int l, r;q--;){
		cin >> l >> r;
		if(lst[l] <= r) cout << "NO\n";
		else cout << "YES\n";
	}

	return 0;
}

Compilation message (stderr)

Joker.cpp: In function 'void restore(int)':
Joker.cpp:63:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(md.size() > _sz) rollback();
        ~~~~~~~~~~^~~~~

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