Submission #138984

#	Time	Username	Problem	Language	Result	Execution time	Memory
138984		StevenH	Mecho (IOI09_mecho)	C++14	100 / 100	520 ms	9084 KiB

mecho

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
struct Node{
	int x,y,tm;
};
int n,s;
int vis[805][805];
int _map[805][805];
int map[805][805];
int side[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
queue<Node> _bee;
queue<Node> bee;
void print()
{
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)cout<<map[i][j];
		cout<<endl;
	}
	cout<<endl;
}
void reset()
{
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			map[i][j]=_map[i][j];
	bee=_bee;
	memset(vis,0,sizeof(vis));
}
void runbee(int t)
{
	if(t==0)return;
	int btm=bee.front().tm;
	while(!bee.empty())
	{
		Node res=bee.front();
		int x=res.x;
		int y=res.y;
		int tm=res.tm;
		if(res.tm==btm+t)break;
		bee.pop();
		//cout<<x<<" "<<y<<endl;
		for(int i=0;i<4;i++)
		{
			int newx=x+side[i][0];
			int newy=y+side[i][1];
			//cout<<" "<<newx<<" "<<newy<<endl;
			if(newx<0 || newy<0 || newx>=n || newy>=n)continue;
			if(map[newx][newy]==0 || map[newx][newy]==2)
			{
				bee.push({newx,newy,tm+1});
				map[newx][newy]=3;
			}
		}
	}
}

bool bfs(int sx,int sy,int t)
{
	reset();
	runbee(t);
	queue<Node> que;
	if(map[sx][sy]==3)return 0;
	que.push({sx,sy,0});
	vis[sx][sy]=1;
	int nowt=0;
	int x,y;
	while(!que.empty())
	{
		Node res=que.front();
		que.pop();
		x=res.x;
		y=res.y;
		int tm=res.tm;
		if(res.tm>nowt && res.tm%s==0)runbee(1);
		nowt=res.tm;
		if(map[x][y]==3)continue;
		if(map[x][y]==4)return 1;
		for(int i=0;i<4;i++)
		{
			int newx=x+side[i][0];
			int newy=y+side[i][1];
			if(newx<0 || newy<0 || newx>=n || newy>=n)continue;
			if(map[newx][newy]==3 || map[newx][newy]==1)continue;
			if(vis[newx][newy])continue;
			que.push({newx,newy,tm+1});
			vis[newx][newy]=1;
		}
	}
	return 0;
}

int main()
{
	//freopen("./data/mecho.092.in","rb",stdin);
	cin>>n>>s;

	int sx,sy;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			char res;
			cin>>res;
			if(res=='G')_map[i][j]=0;
			else if(res=='T')_map[i][j]=1;
			else if(res=='M')_map[i][j]=2,sx=i,sy=j;
			else if(res=='H')_map[i][j]=3,_bee.push({i,j,0});
			else if(res=='D')_map[i][j]=4;
		}
	}	

	if(!bfs(sx,sy,0))cout<<"-1"<<endl;
	else
	{
		if(!bfs(sx,sy,1))cout<<"0"<<endl;
		else
		{
			int left=1,right=1;
			while(bfs(sx,sy,right))left=right,right*=2;
			if(right==1)cout<<"1"<<endl;
			else
			{
				right--;
				while(left<right)
				{
					int mid=(left+right)/2;
					if((left+right)%2==1)mid++;
					if(bfs(sx,sy,mid))left=mid;
					else right=mid-1;
				}
				cout<<left<<endl;
			}
		}
	}

	return 0;
}

Compilation message (stderr)

mecho.cpp: In function 'int main()':
mecho.cpp:118:10: warning: 'sy' may be used uninitialized in this function [-Wmaybe-uninitialized]
   if(!bfs(sx,sy,1))cout<<"0"<<endl;
       ~~~^~~~~~~~~
mecho.cpp:118:10: warning: 'sx' may be used uninitialized in this function [-Wmaybe-uninitialized]

• Subtask 1: 100 / 100