제출 #1326099

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326099		boclobanchat	Joker (BOI20_joker)	C++20	14 / 100	2096 ms	10712 KiB

Joker

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
const int sqr=300;
struct DSU
{
	int dsu[MAXN*3];
	bool F[MAXN*3];
	pair<int,bool> root(int i)
	{
		if(!dsu[i]) return {i,F[i]};
		pair<int,bool> res=root(dsu[i]);
		return {dsu[i]=res.first,F[i]^=res.second};
	}
	bool merge(int i,int j)
	{
		pair<int,bool> a=root(i),b=root(j);
		if((i=a.first)==(j=b.first)) return (a.second==b.second);
		dsu[j]=i,F[j]=(a.second==b.second);
		return false;
	}
};
DSU A,B;
pair<int,int> E[MAXN],Q[MAXN];
vector<int> vi[MAXN/sqr+5][MAXN/sqr+5];
bool ans[MAXN];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,m,q;
	cin>>n>>m>>q;
	for(int i=1;i<=m;i++) cin>>E[i].first>>E[i].second;
	for(int i=1;i<=q;i++)
	{
		int l,r;
		cin>>l>>r;
		vi[(l-1)/sqr][(r-1)/sqr].push_back(i),Q[i]={l,r};
	}
	for(int i=0;i*sqr+1<=m;i++)
	{
		bool ck=false;
		for(int j=1;j<=n;j++) A.dsu[j]=A.F[j]=0;
		for(int j=1;j<=i*sqr;j++) ck|=A.merge(E[j].first,E[j].second);
		int r=m;
		for(int j=(m-1)/sqr;j>=i;j--)
		{
			if(ck) for(auto v:vi[i][j]) ans[v]=true;
			else for(auto v:vi[i][j])
			{
				bool e=false;
				for(int idx=i*sqr+1;idx<Q[v].first;idx++)
				{
					int l=E[idx].first,r=E[idx].second;
					pair<int,int> x=A.root(l),y=A.root(r);
					e|=B.merge(x.first,x.first+n);
					e|=B.merge(y.first,y.first+n);
					e|=B.merge(x.first+n*x.second,l+n*2);
					e|=B.merge(y.first+n*y.second,r+n*2);
					e|=B.merge(l+n*2,r+n*2);
				}
				for(int idx=Q[v].second+1;idx<=r;idx++)
				{
					int l=E[idx].first,r=E[idx].second;
					pair<int,int> x=A.root(l),y=A.root(r);
					e|=B.merge(x.first,x.first+n);
					e|=B.merge(y.first,y.first+n);
					e|=B.merge(x.first+n*x.second,l+n*2);
					e|=B.merge(y.first+n*y.second,r+n*2);
					e|=B.merge(l+n*2,r+n*2);
				}
				for(int idx=i*sqr+1;idx<Q[v].first;idx++)
				{
					int l=E[idx].first,r=E[idx].second;
					pair<int,int> x=A.root(l),y=A.root(r);
					B.dsu[x.first]=B.F[x.first]=0;
					B.dsu[x.first+n]=B.F[x.first+n]=0;
					B.dsu[y.first]=B.F[y.first]=0;
					B.dsu[y.first+n]=B.F[y.first+n]=0;
					B.dsu[l+n*2]=B.F[l+n*2]=0;
					B.dsu[r+n*2]=B.F[r+n*2]=0;
				}
				for(int idx=Q[v].second+1;idx<=r;idx++)
				{
					int l=E[idx].first,r=E[idx].second;
					pair<int,int> x=A.root(l),y=A.root(r);
					B.dsu[x.first]=B.F[x.first]=0;
					B.dsu[x.first+n]=B.F[x.first+n]=0;
					B.dsu[y.first]=B.F[y.first]=0;
					B.dsu[y.first+n]=B.F[y.first+n]=0;
					B.dsu[l+n*2]=B.F[l+n*2]=0;
					B.dsu[r+n*2]=B.F[r+n*2]=0;
				}
				ans[v]=e;
			}
			while(r>j*sqr) ck|=A.merge(E[r].first,E[r].second),r--;
		}
	}
	for(int i=1;i<=q;i++) if(ans[i]) cout<<"YES\n";
	else cout<<"NO\n";
}

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