Submission #698960

#	Time	Username	Problem	Language	Result	Execution time	Memory
698960		safaricola	Alternating Heights (CCO22_day1problem1)	C++17	11 / 25	230 ms	13812 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 1; i <= n; i++) 
#define pb push_back
int n,a[3010],st=2,k,q,top[3010],cur,mini[3010],x,y;
bool rmv[3010][3010],vis[3010];
vector<int> adjl[3010];
bool ord(int a){
	if(vis[a] && top[a]==-1) return true;
	if(vis[a]) return false;
	vis[a] = true;
	for (int it: adjl[a]){
		if(rmv[a][it])continue;
	  if(ord(it)){
	  	return true;
	  }
	}
	cur++;
	top[a]=cur;
	return false;
}
void remov(){
	bool flag=true;
	while(flag){
		flag=false;
		cur=0;
		memset(top, -1, sizeof(top));
		memset(vis, 0, sizeof(vis));
		for(int i=1; i<=n; i++)
			if(!vis[i]) 
				if(ord(i)){
					flag=true;
					i=n+1;
					break;
				}
		if(flag){
			//cout<<st<<">\n";
			//remove edge;
			assert(st<=n+1);
			if(st%2==1){
				rmv[a[st]][a[st-1]]=1;
			}else{
				rmv[a[st-1]][a[st]]=1;
			}/*
			rep(i,n)
			for (int it: adjl[i]){
				if(rmv[i][it]) cout<<"rem "<<i<<' '<<it<<endl;
				else cout<<i<<' '<<it<<endl;
			}*/
			st++;
		}
	}
}
int main(){
	 ios_base::sync_with_stdio(false);cin.tie(0);
	cin>>n>>k>>q;
	mini[1]=1;
	rep(i,n){
		cin>>a[i];
		if(i==1)continue;
		if(i%2==1){
			adjl[a[i]].pb(a[i-1]);
			rmv[a[i]][a[i-1]]=0;
			remov();
			//cout<<"ans:"<<st<<' '<<i<<endl;
			mini[i]=st-1;
		}else{
			adjl[a[i-1]].pb(a[i]);
			rmv[a[i-1]][a[i]]=0;
			remov();
			//cout<<"ans:"<<st<<' '<<i<<endl;
			mini[i]=st-1;
		}
	}
	while(q--){
		cin>>x>>y;
		if(x<mini[y])cout<<"NO\n";
		else cout<<"YES\n";
	}
}
/*
6 3 3
1 1 2 3 1 2
1 2
2 5
2 6
* 
6 3 3
1 1 1 1 1 1
1 2
2 5
2 6
* 
10 2 3
1 1 2 1 1 1 1 2 2 2
*/

• Subtask 1: 4 / 4
• Subtask 2: 0 / 6
• Subtask 3: 7 / 7
• Subtask 4: 0 / 8