제출 #439518

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
439518		soroush	Joker (BOI20_joker)	C++17	0 / 100	228 ms	9788 KiB

Joker

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int , int> pii;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 2e5+10;
const ll mod = 1e9+7;

#define pb push_back
#define endl '\n'
#define dokme(x) cout << x , exit(0)
#define ms(x , y) memset(x , y , sizeof x)
ll pw(ll a, ll b, ll md = mod){ll res = 1;while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);}

int n, m, q;
int a[maxn], b[maxn];
int par[maxn], sz[maxn];
bool val[maxn];
int mn[maxn];

int getpar(int v){
	return ((~par[v]) ? getpar(par[v]) : v);
}

bool getval(int v){
	return ((~par[v]) ? val[v] ^ getval(par[v]) : val[v]);
}

bool ok = 0;

vector < int > PAR;

void merge(int x){
	int u = a[x] , v = b[x];
	int pu = getpar(u) , pv = getpar(v);
	if(pu == pv){
		if(!ok and getval(u) == getval(v))
			PAR.pb(0);
		else
			PAR.pb(-1);
		ok |= getval(u) == getval(v);
		return;
	}
	if(sz[pu] > sz[pv])swap(pu , pv);
	PAR.pb(pu);
	val[pu] ^= getval(v) == getval(u);
	par[pu] = pv;
	sz[pv] += sz[pu];
}

void rollback(){
	int v = PAR.back();
	PAR.pop_back();
	if(v == -1)return;
	if(v == 0){
		ok = 0;
		return;
	}
	sz[par[v]] -= sz[v];
	par[v] = -1;
	
}

int L = 0 , R = 0;

void solve(int l , int r , int ul , int ur){
	if(l > r)return;
	if(ok) return;
	if(L ^ (l - 1))dokme("wf");
	assert(L == l - 1 and R == ur + 1);
	int mid = (l + r) / 2;
	while(L + 1 < mid){
		L++;
		merge(L);
	}if(ok)mn[mid] = m + 1;
	while(!ok){
		mn[mid] = R;
		R --;
		merge(R);
	}
	assert(ok);
	while(R < ur + 1)rollback(), R ++;
	while (L + 1 <= mid)L++, merge(L);
	assert(L == mid and R == ur + 1);
	solve(mid + 1 , r , mn[mid] , ur);
	assert(L == mid and R == ur + 1);
	while(L >= l){
		rollback() , L --;
	}
	while(R > mn[mid] + 1){
		merge(--R);
	}
	assert(L == l - 1 and R == min(m , mn[mid]) + 1);
	solve(l , mid - 1 , ul , min(m , mn[mid]));
	assert(L == l - 1 and R == min(m , mn[mid]) + 1);
	while(R < ur + 1){
		rollback(), R ++;
	}
	assert(L == l- 1 and R == ur + 1);
}

int32_t main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin >> n >> m >> q;
	ms(par, -1);
	for(int i = 1 ; i <= n ; i ++)sz[i] = 1;
	for(int i = 1 ; i <= m ; i ++)
		cin >> a[i] >> b[i], merge(i);
	R = m + 1;
	cerr << endl;
	if(ok){
		for(int i = 1 ; i <= n ; i ++)sz[i] = 1;
		ms(par, -1) , ms(val , 0) , ok = 0;
		solve(1 , m , 1 , m);
	}
	while(q --){
		int l , r;
		cin >> l >> r;
		if(mn[l] == 0)mn[l] = m + 1;
		cout << ((r < mn[l] - 1) ? "YES" : "NO") << endl;
	}
	return(0);
}

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