Submission #1342892

#TimeUsernameProblemLanguageResultExecution timeMemory
1342892vjudge1Toy (CEOI24_toy)C++20
100 / 100
72 ms42240 KiB
#include <bits/stdc++.h>
using namespace std;
#define ll long long
pair<ll,ll>e,wer;
vector<vector<ll>>c,f;
vector<vector<bool>>ce;
map<pair<ll,ll>,bool>m;
ll w,h,k,l;
bool be=0;
vector<ll>dx= {1,-1,0,0};
vector<ll>dy= {0,0,1,-1};
void bfs(ll a,ll b)
{
	//cout<<4<<endl;
	queue<pair<ll,ll>>q;
	q.push({a,b});
	ce[a][b]=1;
	//cout<<8<<endl;
	while(!q.empty())
	{
		//cout<<5<<endl;
		auto [u,ke]=q.front();
		q.pop();
		if(u==e.first && ke==e.second)
		{
			be=1;
			return;
		}
		auto xsy=upper_bound(c[u].begin(),c[u].end(),ke);
		ll sol,sag;
		if(c[u].empty() || xsy==c[u].end())
		{
			sol=w+1;
		}
		else
			sol=*xsy;
		if(xsy==c[u].begin())
		{
			sag=-1;
		}
		else
			sag=*(--xsy);
		auto xyz=lower_bound(f[ke].begin(),f[ke].end(),u);
		ll as,yu;
		if(f[ke].empty() || xyz==f[ke].end())
		{
			yu=h+1;
		}
		else
			yu=*xyz;
		if(xyz==f[ke].begin())
		{
			as=-1;
		}
		else
			as=*(--xyz);
		for(int i=0; i<4; i++)
		{
			ll r=u+dx[i],o=dy[i]+ke;
			if(r<=h && o<=w && r>=0 && o>=0 && !ce[r][o])
			{
				auto xs=lower_bound(c[r].begin(),c[r].end(),o);
				ll p,n;
				if(c[r].empty() || xs==c[r].end())
				{
					n=w+1;
				}
				else
					n=*xs;
				if(xs==c[r].begin())
				{
					p=-1;
				}
				else
					p=*(--xs);
				//cout<<r<<' '<<o<<' '<<n<<' '<<p<<endl;
				if(min(n,sol)-max(p,sag)<=k)
					continue;
				auto xy=lower_bound(f[o].begin(),f[o].end(),r);
				ll pu,nu;
				if(f[o].empty() || xy==f[o].end())
				{
					nu=h+1;
				}
				else
					nu=*xy;
				if(xy==f[o].begin())
				{
					pu=-1;
				}
				else
					pu=*(--xy);
				if(min(nu,yu)-max(as,pu)<=l)
					continue;
				q.push({r,o});
				ce[r][o]=1;
			}
		}
	}
}
int main()
{
	cin>>w>>h>>k>>l;
	//cout<<h<<endl;
	//cout<<k<<endl;
	w--;
	h--;
	ll z,x,g,rew;
	cin>>z>>x>>g>>rew;
	ce.assign(h+2,vector<bool>(w+2));
	c.assign(h+1, {});
	f.assign(w+1, {});
	for(int i=0; i<=h; i++)
	{
		string s;
		cin>>s;
		//cout<<s<<endl;
		for(int j=0; j<=w; j++)
		{
			if(s[j]=='*')
			{
				e= {i,j};
			}
			else if(s[j]=='X')
			{
				c[i].push_back(j);
				f[j].push_back(i);
			}
			//cout<<s[j];
		}
		//cout<<endl;
	}
	//cout<<c[0][0]<<endl;
	for(int i=0; i<c.size(); i++)
	{
		if(c[i].empty())
			continue;
		sort(c[i].begin(),c[i].end());
	}
	for(int i=0; i<f.size(); i++)
	{
		if(f[i].empty())
			continue;
		sort(f[i].begin(),f[i].end());
		//for(int j=0;j<f[i].size();j++)
		//cout<<i<<' '<<f[i][j]<<endl;
	}
	bfs(x,g);
	if(be)
		cout<<"YES"<<endl;
	else
		cout<<"NO"<<endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...