Submission #138682

#	Time	Username	Problem	Language	Result	Execution time	Memory
138682		20160161simone	Mecho (IOI09_mecho)	C++14	100 / 100	348 ms	12124 KiB

mecho

#include <bits/stdc++.h>
#define N 810
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
ll read()
{
	char c=getchar();bool flag=0;ll x=0;
	while(c<'0'||c>'9'){if(c=='-')flag=1;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
	return flag?-x:x;
}
queue<ll> q;
char a[N][N];
ll b[N][N],vis[N][N]; 
int ax[4]={1,0,-1,0},n,s,sx,sy,ex,ey;
int ay[4]={0,1,0,-1};
void bfs()
{
	while(q.size()!=0)
	{
		ll x=q.front()/N,y=q.front()%N;
		q.pop();
		for(ll i=0;i<4;i++)
		{
			//cout<<"++";
			ll dx=x+ax[i];
			ll dy=y+ay[i];
			if(a[dx][dy]=='G'&&b[dx][dy]==-1)
			{
				//cout<<"++";
				b[dx][dy]=b[x][y]+s;
				q.push(dx*N+dy);
			}	
		} 
	}
}
bool check(ll mid)
{
	for(ll i=1;i<=n;i++)
	{
		for(ll j=1;j<=n;j++) vis[i][j]=-1;
	}
	//cout<<"++";
	if(b[sx][sy]<=mid*s) return 0;
	//cout<<"++"; 
	vis[sx][sy]=mid*s;
	q.push(sx*N+sy);
	while(q.size()!=0)
	{
		ll x=q.front()/N,y=q.front()%N;
		q.pop();
		//cout<<"++"; 
		for(ll i=0;i<4;i++)
		{
			ll dx=x+ax[i];
			ll dy=y+ay[i];
			if((a[dx][dy]=='G'&&vis[dx][dy]==-1 && b[dx][dy]>vis[x][y]+1)||(a[dx][dy]=='D'&&vis[dx][dy]==-1))
			{
				//cout<<"++";
				vis[dx][dy]=vis[x][y]+1;
				q.push(dx*N+dy);
			}
		} 
	} 
	return vis[ex][ey]!=-1;
}
int main()
{
	n=read(),s=read();
	for(ll i=1;i<=n;i++)
	{
		for(ll j=1;j<=n;j++) b[i][j]=-1;
	}
	for(ll i=1;i<=n;i++)
	{
		for(ll j=1;j<=n;j++)
		{
			cin>>a[i][j];
			if(a[i][j]=='M') sx=i,sy=j,a[i][j]='G';
			if(a[i][j]=='D') ex=i,ey=j;
			if(a[i][j]=='H') q.push(i*N+j),b[i][j]=0;
		}
	}
	/*for(ll i=1;i<=n;i++)
	{
		for(ll j=1;j<=n;j++) cout<<a[i][j];
		cout<<endl; 
	}*/
	bfs();
	ll r=n*n,l=0,ans=-1;
	while(l<=r)
	{
		ll mid=(l+r)/2;
		if(check(mid)) ans=mid,l=mid+1;
		else r=mid-1;
	}
	printf("%lld",ans);
}

• Subtask 1: 100 / 100