Submission #1326133

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326133		boclobanchat	Joker (BOI20_joker)	C++20	0 / 100	2093 ms	7664 KiB

Joker

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
int dsu[MAXN],cnt[MAXN],F[MAXN],R[MAXN],cc=0;
stack< pair<int,int> > st;
pair<int,int> edge[MAXN];
int root(int i)
{
	if(!dsu[i]) return i;
	return root(dsu[i]);
}
int getval(int i)
{
	if(!dsu[i]) return F[i];
	return F[i]^getval(dsu[i]);
}
void merge(int i,int j)
{
	int a=getval(i),b=getval(j);
	if((i=root(i))==(j=root(j)))
	{
		cc+=(a==b),st.push({-1,a==b});
		return ;
	}
	if(cnt[i]<cnt[j]) swap(i,j);
	dsu[j]=i,cnt[i]+=cnt[j],F[j]=(a==b),st.push({i,j});
}
void rollback()
{
	int x=st.top().first,y=st.top().second;
	st.pop();
	if(x==-1) cc-=y;
	else dsu[y]=F[y]=0,cnt[x]-=cnt[y];
}
void solve(int l,int r,int pl,int pr)
{
	if(l>r) return ;
	int mid=(l+r)/2;
	for(int i=l-1;i<mid;i++) if(i) merge(edge[i].first,edge[i].second);
	R[mid]=pr;
	while(!cc) merge(edge[R[mid]].first,edge[R[mid]].second),R[mid]--;
	if(cc) R[mid]++,rollback();
	if(l==r)
	{
		int res=R[mid];
		while(res<pr) res++,rollback();
		for(int i=mid-1;i>=l-1;i--) if(i) rollback();
		return ;
	}
	int res=R[mid];
	while(res<pr) res++,rollback();
	solve(mid+1,r,R[mid],pr);
	for(int i=mid-1;i>=l-1;i--) if(i) rollback();
	while(res>R[mid]) merge(edge[res].first,edge[res].second),res--;
	solve(l,mid-1,pl,R[mid]);
	while(res<pr) res++,rollback();
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,m,q;
	cin>>n>>m>>q;
	int p=m;
	for(int i=1;i<=m;i++) cin>>edge[i].first>>edge[i].second;
	for(int i=1;i<=m;i++)
	{
		merge(edge[i].first,edge[i].second);
		if(cc)
		{
			for(int j=i;j<=m;j++) R[j]=m+1;
			p=i-1;
			break;
		}
	}
	if(!cc) for(int i=1;i<=m;i++) R[i]=i-1;
	else
	{
		while(!st.empty()) rollback();
		solve(1,p,1,m);
	}
	for(int i=1;i<=q;i++)
	{
		int l,r;
		cin>>l>>r;
		if(R[l]<=r) cout<<"NO\n";
		else cout<<"YES\n";
	}
}

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