제출 #480085

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
480085		AdamGS	Joker (BOI20_joker)	C++14	100 / 100	452 ms	15136 KiB

Joker

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=2e5+7;
struct operacje {
	int a, ilea, b, ileb, zmianacyklu;
};
pair<int,int>F[LIM], kraw[LIM];
int ile[LIM], T[LIM], cykl, n, m, q;
stack<operacje>S;
pair<int,int>fnd(int x) {
	if(F[x].st==x) return F[x];
	pair<int,int>ans=fnd(F[x].st);
	ans.nd^=F[x].nd;
	return ans;
}
void uni(int a, int b) {
	pair<int,int>x=fnd(a), y=fnd(b);
	operacje p={x.st, ile[x.st], y.st, ile[y.st], 0};
	if(x.st==y.st) {
		if(x.nd==y.nd) {
			++cykl;
			p.zmianacyklu=1;
		}
		S.push(p);
		return;
	}
	if(ile[x.st]>ile[y.st]) swap(x, y);
	ile[y.st]+=ile[x.st];
	F[x.st]={y.st, x.nd==y.nd};
	S.push(p);
}
void usun(int x) {
	while(x--) {
		operacje p=S.top(); S.pop();
		F[p.a]={p.a, 0};
		ile[p.a]=p.ilea;
		F[p.b]={p.b, 0};
		ile[p.b]=p.ileb;
		cykl-=p.zmianacyklu;
	}
}
void dodaj(int l, int r) {
	while(l<=r) {
		uni(kraw[l].st, kraw[l].nd);
		++l;
	}
}
void dc(int l, int r, int x) {
	int mid=(l+r)/2, p=x+1;
	dodaj(l, mid-1);
	while(!cykl) {
		--p;
		dodaj(p, p);
	}
	usun(x-p+1);
	if(l==r) {
		T[l]=p;
		return;
	}
	usun(mid-l);
	dodaj(p+1, x);
	dc(l, mid, min(p, x));
	usun(max(0, x-p));
	dodaj(l, mid);
	dc(mid+1, r, x);
	usun(mid-l+1);
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m >> q;
	rep(i, n) {
		F[i]={i, 0};
		ile[i]=1;
	}
	rep(i, m) {
		cin >> kraw[i].st >> kraw[i].nd;
		--kraw[i].st;
		--kraw[i].nd;
	}
	dodaj(0, m-1);
	if(!cykl) {
		while(q--) cout << "NO\n";
		return 0;
	}
	usun(m);
	dc(0, m-1, m-1);
	while(q--) {
		int a, b;
		cin >> a >> b; --a; --b;
		cout << (b<T[a]?"YES":"NO") << '\n';
	}
}

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