Submission #893175

#	Time	Username	Problem	Language	Result	Execution time	Memory
893175		amirhoseinfar1385	Joker (BOI20_joker)	C++17	100 / 100	119 ms	6768 KiB

Joker

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#include<bits/stdc++.h>
using namespace std;
const unsigned int maxn=200000+10;
unsigned int n,m,q,dp[maxn],f;
pair<unsigned int,unsigned int>alle[maxn];

struct dsu{
	vector<unsigned int>ha;
	unsigned int par[maxn],sz[maxn];
	unsigned char val[maxn];
	dsu(){
		for(unsigned int i=0;i<maxn;i++){
			par[i]=i;
			sz[i]=1;
		}
	}
	unsigned int root(unsigned int u){
		while(u!=par[u]){
			u=par[u];
		}
		return u;
	}
	unsigned char len(unsigned int u){
		unsigned int ret=0;
		while(u!=par[u]){
			ret+=val[u];
			u=par[u];
		}
		return ret;
	}

	void con(unsigned int u,unsigned int v){
		unsigned int rootu=root(u),rootv=root(v);
		if(rootu!=rootv){
			if(sz[rootu]<sz[rootv]){
				swap(rootu,rootv);
				swap(u,v);
			}
			unsigned char lu=len(u),lv=len(v);
			par[rootv]=rootu;
			sz[rootu]+=sz[rootv];
			if((lu&1)==(lv&1)){
				val[rootv]=1;
			}
			else{
				val[rootv]=0;
			}
			ha.push_back(rootv);
			return ;
		}
		ha.push_back(0);
	}
	bool two(unsigned int u,unsigned int v){
		unsigned int rootu=root(u),rootv=root(v);
		if(rootu!=rootv){
			return 0;
		}
		unsigned char  lu=len(u),lv=len(v);
		if((lu&1)==(lv&1)){
			return 1;
		}
		return 0;
	}
	void back(){
		if((unsigned int)ha.back()==0){
			ha.pop_back();
			return ;
		}
		unsigned int x=ha.back();
		sz[par[x]]-=sz[x];
		par[x]=x;
		val[x]=0;
		ha.pop_back();
		return ;
	}
}ds;

void solve(unsigned int l,unsigned int r,unsigned int tl,unsigned int tr){
	if(l>r){
		return ;
	}
	if(tl==tr){
		for(unsigned int i=l;i<=r;i++){
			dp[i]=tl;
		}
		return ;
	}
	unsigned int opt=0;
	unsigned int now=ds.ha.size();
	unsigned int mid=(l+r)>>1;
	for(unsigned int i=l;i<=mid;i++){
		ds.con(alle[i].first,alle[i].second);
	}
	for(unsigned int i=tr;i>=tl;i--){
		if(ds.two(alle[i].first,alle[i].second)){
			opt=i;
			break;
		}
		ds.con(alle[i].first,alle[i].second);
	}
	dp[mid]=opt;
	while((unsigned int)ds.ha.size()>now){
		ds.back();
	}
	for(unsigned int i=l;i<=mid;i++){
		ds.con(alle[i].first,alle[i].second);
	}
	solve(mid+1,r,opt,tr);
	while((unsigned int)ds.ha.size()>now){
		ds.back();
	}
	for(unsigned int i=tr;i>opt;i--){
		ds.con(alle[i].first,alle[i].second);
	}
	solve(l,mid-1,tl,opt);
	while((unsigned int)ds.ha.size()>now){
		ds.back();
	}
}

unsigned int pre(){
	for(unsigned int i=1;i<=m;i++){
		if(ds.two(alle[i].first,alle[i].second)){
			return i;
		}
		ds.con(alle[i].first,alle[i].second);
	}
	return m+1;
}

unsigned int suf(){
	for(unsigned int i=m;i>=0;i--){
		if(ds.two(alle[i].first,alle[i].second)){
			return i;
		}
		ds.con(alle[i].first,alle[i].second);
	}
	return 0;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);	
	cin>>n>>m>>q;
	for(unsigned int i=1;i<=m;i++){
		cin>>alle[i].first>>alle[i].second;
	}
	unsigned int ind=pre();
	while((unsigned int)ds.ha.size()>0){
		ds.back();
	}
	solve(1,ind-1,0,m);
	for(unsigned int i=ind;i<=m;i++){
		dp[i]=m+2;
	}
	if((unsigned int)ds.ha.size()!=0){
		assert(0);
	}
	dp[0]=suf();
	for(unsigned int i=0;i<q;i++){
		unsigned int l,r;
		cin>>l>>r;
		if(dp[l-1]<=r){
			cout<<"NO\n";
		}
		else{
			cout<<"YES\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