Submission #877415

#	Time	Username	Problem	Language	Result	Execution time	Memory
877415		anhduc2701	Joker (BOI20_joker)	C++17	0 / 100	704 ms	262144 KiB

Joker

#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second 
using namespace std;
typedef long long ll;
const int maxn=2e5+5;
int n,m,q;
pair<int,int> ed[maxn];
int sz[maxn];
int pa[maxn];
int col[maxn];
int last[maxn];
struct DSU{
	int u,v;
	bool ok;
	DSU(int _u,int _v,bool _ok){
		u=_u;
		v=_v;
		ok=_ok;
	}
};
pair<int,int> fin(int x){
	if(pa[x]==x){
		return {x,0};
	}
	pair<int,int> k=fin(pa[x]);
	return {k.fi,k.se^col[x]};
}
stack<DSU>st;
int ok=0;
bool join(int u,int v){
	pair<int,int>x=fin(u);
	pair<int,int>y=fin(v);
	if(x.fi==y.fi){
		st.push(DSU(-1,y.fi,ok));
		if(x.se==y.se){
			ok=1;
		}
		return false;
	}
	if(sz[x.fi]>sz[y.fi]){
		swap(x,y);
		swap(u,v);
	}
	st.push(DSU(x.fi,y.fi,ok));
	pa[y.fi]=x.fi;
	col[y.fi]=col[x.se]^col[y.se]^1;
	return true;
}
void rollback(){
	DSU k=st.top();
	st.pop();
	if(k.u!=-1){
		pa[k.v]=k.v;
		sz[k.u]-=sz[k.v];
		col[k.v]=0;
	}
	ok=k.ok;
}
void rev(int l,int r,int optl,int optr){
	if(l>r || optl>optr)return;
	int mid=(l+r)/2;
	int cnta=0;
	for(int i=l;i<=mid-1;i++){
		cnta+=join(ed[i].fi,ed[i].se);
		// cout << ed[i].fi << ' ' << ed[i].se << '\n';
		if(ok==1){
			last[mid]=optr;
			break;
		}
	}
	int cntb=0;
	for(int i=optr-1;i>=max(mid,optl);i--){
		cntb+=join(ed[i].fi,ed[i].se);
		if(ok==1){	
			last[mid]=i+1;
			break;
		}
	}
	for(int i=1;i<=cnta+cntb;i++){
		rollback();
	}
	cntb=0;
	for(int i=last[mid]+1;i<=optr-1;i++){
		cntb+=join(ed[i].fi,ed[i].se);
	}	
	rev(l,mid-1,optl,last[mid]);
	for(int i=1;i<=cntb;i++){
		rollback();
	}
	cnta=0;
	for(int i=l;i<=mid;i++){
		cnta+=join(ed[i].fi,ed[i].se);
	}
	rev(mid+1,r,last[mid],optr);
	for(int i=1;i<=cnta;i++){
		rollback();
	}
}
signed main(){
	// freopen("input.inp","r",stdin);
	// freopen("output.out","w",stdout);
	cin.tie(0),cout.tie(0)->sync_with_stdio(0);
	cin >> n >> m >> q;
	for(int i=1;i<=m;i++){
		cin >> ed[i].fi >> ed[i].se;
	}
	for(int i=1;i<=n;i++){
		pa[i]=i;
		sz[i]=1;
	}
	rev(1,m,1,m+1);
	for(int i=1;i<=q;i++){
		int lt,rt;
		cin >> lt >> rt;
		if(last[lt]<=rt+1){
			cout << "NO\n";
		}
		else{
			cout << "YES\n";
		}
	}
}

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