oj.uz

Submission #893152

# Submission time Handle Problem Language Result Execution time Memory
893152 2023-12-26T15:06:15 Z amirhoseinfar1385 Joker (BOI20_joker) C++17
0 / 100
 2000 ms 7464 KB 
#include<bits/stdc++.h>
using namespace std;
const int maxn=200000+10;
int n,m,q,dp[maxn];
pair<int,int>alle[maxn];

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

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

void solve(int l,int r,int tl,int tr){
	if(l>r){
		return ;
	}
	if(tl==tr){
		for(int i=l;i<=r;i++){
			dp[i]=tl;
		}
		return ;
	}
	int opt=0;
	int now=ds.ha.size();
	int mid=(l+r)>>1;
	for(int i=l;i<=mid;i++){
		ds.con(alle[i].first,alle[i].second);
	}
	for(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);
	}
//	cout<<l<<" "<<r<<" "<<tl<<" "<<tr<<" "<<mid<<" "<<opt<<" "<<now<<"\n";
	dp[mid]=opt;
	while((int)ds.ha.size()>now){
		ds.back();
	}
	for(int i=l;i<=mid;i++){
		ds.con(alle[i].first,alle[i].second);
	}
	solve(mid+1,r,opt,tr);
	while((int)ds.ha.size()>now){
		ds.back();
	}
	for(int i=tr;i>opt;i--){
		ds.con(alle[i].first,alle[i].second);
	}
	solve(l,mid-1,tl,opt);
	while((int)ds.ha.size()>now){
		ds.back();
	}
}

int pre(){
	for(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;
}

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

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 2 ms 4700 KB Output is correct
4 Incorrect 1 ms 4700 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 2 ms 4700 KB Output is correct
4 Incorrect 1 ms 4700 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Execution timed out 2044 ms 7464 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 2 ms 4700 KB Output is correct
4 Incorrect 1 ms 4700 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 2 ms 4700 KB Output is correct
4 Incorrect 1 ms 4700 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 2 ms 4700 KB Output is correct
4 Incorrect 1 ms 4700 KB Output isn't correct
5 Halted 0 ms 0 KB -