Submission #1140686

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140686		MuhammadSaram	Toy (CEOI24_toy)	C++20	35 / 100	1594 ms	875576 KiB

Main

#include <bits/extc++.h>

using namespace std;
using namespace __gnu_pbds;

const int M = 1500;

struct has
{
	long long operator() (pair<int,int> p) const
	{
		return 1ll*p.first*(1000003)+p.second;
	}
};

int pre[M+1][M+1],n,m,h,v,tx,ty;
cc_hash_table<pair<int,int>,bool,has> se;
unordered_set<int> it;

bool clr(int x,int y,int x1,int y1)
{
	if (x>=0 && y>=0 && x1<n && y1<m)
		return pre[x1+1][y1+1]-pre[x][y1+1]-pre[x1+1][y]+pre[x][y]==0;
	return 0;
}

void dfs(int vr,int hr)
{
	se[{vr,hr}]=1;
	int xh=hr/M,yh=hr%M,xv=vr/M,yv=vr%M;
	if (xh==tx && yv==ty)
	{
		cout<<"YES"<<endl;
		exit(0);
	}
	if (yh<yv && clr(xh,yh+1,xh,yh+h))
	{
		if (se.find({vr,hr+1})==se.end()) dfs(vr,hr+1);	
	}
	if (yv<yh+h-1 && clr(xh,yh-1,xh,yh+h-2))
	{
		if (se.find({vr,hr-1})==se.end()) dfs(vr,hr-1);
	}
	if (xh<xv+v-1 && clr(xh+1,yh,xh+1,yh+h-1))
	{
		if (se.find({vr,hr+M})==se.end()) dfs(vr,hr+M);
	}
	if (xh>xv && clr(xh-1,yh,xh-1,yh+h-1))
	{
		if (se.find({vr,hr-M})==se.end()) dfs(vr,hr-M);
	}
	if (yv<yh+h-1 && clr(xv,yv+1,xv+v-1,yv+1))
	{
		if (se.find({vr+1,hr})==se.end()) dfs(vr+1,hr);
	}
	if (yv>yh && clr(xv,yv-1,xv+v-1,yv-1))
	{
		if (se.find({vr-1,hr})==se.end()) dfs(vr-1,hr);
	}
	if (xv<xh && clr(xv+1,yv,xv+v,yv))
	{
		if (se.find({vr+M,hr})==se.end()) dfs(vr+M,hr);
	}
	if (xv+v-1>xh && clr(xv-1,yv,xv+v-2,yv))
	{
		if (se.find({vr-M,hr})==se.end()) dfs(vr-M,hr);
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(NULL), cout.tie(NULL);
	
	cin>>m>>n>>h>>v;
	int xh,yh,xv,yv;
	cin>>xh>>yh>>xv>>yv;
	string a[n];
	for (int i=0;i<n;i++)
		cin>>a[i];
	for (int i=0;i<n;i++)
		for (int j=0;j<m;j++)
		{
			pre[i+1][j+1]=pre[i+1][j]+pre[i][j+1]-pre[i][j]+(a[i][j]=='X');
			if (a[i][j]=='*')
				tx=i,ty=j;
		}
	dfs(yv*M+xv,yh*M+xh);
	cout<<"NO"<<endl;
		
	return 0;
}

• Subtask 0: 0 / 0
• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 0 / 9
• Subtask 4: 0 / 29
• Subtask 5: 0 / 27