Submission #1182489

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182489		UmairAhmadMirza	Alternating Heights (CCO22_day1problem1)	C++20	7 / 25	1088 ms	4584 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define ll long long
int const N=3005;
int const mod=1e9+7;

int n,k,q;
int seq[N];
int MX[N];
int MX2[N];
vector<int> adj[N];
int tar=0;
bool killed=0;
bool seen[N];
void dfs(int node){
	if(node==tar)
		killed=1;
	if(seen[node] || killed)
		return;
	seen[node]=1;
	for(int i:adj[node])
		dfs(i);
}
bool con(int a,int b){
	killed=0;
	tar=b;
	for (int i = 0; i <=k; ++i)
		seen[i]=0;
	// cerr<<a<<endl;
	dfs(a);
	return killed;
}
int main(){
	cin>>n>>k>>q;
	for (int i = 1; i <=n; ++i)
		cin>>seq[i];
	for(int s=1;s<=n;s++){
		bool bb=0;
		MX[s]=n;
		for(int i=0;i<=k;i++)
			adj[i].clear();
		for(int i=s+1;i<=n;i++){
			if(bb==0){
				if(con(seq[i],seq[i-1])){
					MX[s]=i-1;
					break;
				}
				adj[seq[i-1]].push_back(seq[i]);
			}
			else{
				if(con(seq[i-1],seq[i])){
					MX[s]=i-1;
					break;
				}
				adj[seq[i]].push_back(seq[i-1]);
			}
			bb^=1;
		}
	}
	for(int s=1;s<=n;s++){
		bool bb=1;
		MX2[s]=n;
		for(int i=0;i<=k;i++)
			adj[i].clear();
		for(int i=s+1;i<=n;i++){
			if(bb==0){
				if(con(seq[i],seq[i-1])){
					MX2[s]=i-1;
					break;
				}
				adj[seq[i-1]].push_back(seq[i]);
			}
			else{
				if(con(seq[i-1],seq[i])){
					MX2[s]=i-1;
					break;
				}
				adj[seq[i]].push_back(seq[i-1]);
			}
			bb^=1;
		}
	}
	while(q--){
		int a,b;
		cin>>a>>b;
		if(max(MX[a],MX2[a])<b)
			cout<<"NO"<<'\n';
		else
			cout<<"YES"<<'\n';
	}
	return 0;
}

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