Submission #1200995

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200995		lufychop20171	Mecho (IOI09_mecho)	C++20	84 / 100	157 ms	28488 KiB

mecho

#include <bits/stdc++.h>

using namespace std;

bool ch=false;
long long n,s,si,sj,ei,ej;
long long a[1000][1000];
long long b[1000][1000];
long long c[1000][1000];
long long d[1000][1000];
long long x[4]={0,0,-1,1};
long long y[4]={-1,1,0,0};

bool bee(long long i,long long j)
{
	return i<1 || j<1 || n<i || n<j || d[i][j]==1 || d[i][j]==3;
}
bool bear(long long i,long long j)
{
	return i<1 || j<1 || n<i || n<j || d[i][j]==1;
}

bool check(long long t)
{
	queue<pair<pair<long long,long long>,pair<long long,long long> > > h;
	h.push({{0,t},{si,sj}});
	c[si][sj]=t;
	while(!h.empty())
	{
		long long t0=h.front().first.first;
		long long t1=h.front().first.second;
		long long t2=h.front().second.first;
		long long t3=h.front().second.second;
		h.pop();
		if(t2==ei && t3==ej)
		{
			while(!h.empty())
			{
				h.pop();
			}
			return true;
		}
		for(int i=0;i<4;i++)
		{
			if(bear(t2+x[i],t3+y[i]))
			{
				continue;
			}
			if(-1<a[t2+x[i]][t3+y[i]] && a[t2+x[i]][t3+y[i]]<=t1+(t0+1)/s)
			{
				continue;
			}
			if(c[t2+x[i]][t3+y[i]]>t1+(t0+1)/s)
			{
				c[t2+x[i]][t3+y[i]]=t1+(t0+1)/s;
				h.push({{(t0+1)%s,t1+(t0+1)/s},{t2+x[i],t3+y[i]}});
			}
		}
	}
	return false;
}

int main(void)
{
	queue<pair<long long,pair<long long,long long> > > h;
	cin>>n>>s;
	for(int i=0;i<=n+100;i++)
	{
		for(int j=0;j<=n+100;j++)
		{
			a[i][j]=-1;
			b[i][j]=-1;
		}
	}
	for(int i=1;i<=n;i++)
	{
		string tt;
		cin>>tt;
		for(int j=1;j<=n;j++)
		{
			if(tt[j-1]=='T')
			{
				a[i][j]=-1;
				b[i][j]=-1;
				d[i][j]=1;
			}
			else
			{
				a[i][j]=INT_MAX;
				b[i][j]=INT_MAX;
				d[i][j]=0;
			}
			if(tt[j-1]=='M')
			{
				si=i;
				sj=j;
				d[i][j]=2;
			}
			else if(tt[j-1]=='D')
			{
				a[i][j]=-1;
				ei=i;
				ej=j;
				d[i][j]=3;
			}
			else if(tt[j-1]=='H')
			{
				h.push({0,{i,j}});
				a[i][j]=0;
				d[i][j]=4;
			}
		}
	}
	while(!h.empty())
	{
		long long t1=h.front().first;
		long long t2=h.front().second.first;
		long long t3=h.front().second.second;
		h.pop();
		for(int i=0;i<4;i++)
		{
			if(bee(t2+x[i],t3+y[i]))
			{
				continue;
			}
			if(a[t2+x[i]][t3+y[i]]>t1+1)
			{
				a[t2+x[i]][t3+y[i]]=t1+1;
				h.push({t1+1,{t2+x[i],t3+y[i]}});
			}
		}
	}
	long long l=0,r=640000000,ans=-1;
	while(l<=r)
	{
		long long mid=l+(r-l)/2;
		for(int i=0;i<n+100;i++)
		{
			for(int j=0;j<n+100;j++)
			{
				c[i][j]=b[i][j];
			}
		}
		if(check(mid))
		{
			l=mid+1;
			ans=mid;
		}
		else
		{
			r=mid-1;
		}
	}
	cout<<ans;
	return 0;
}
/*
7 3
TTTTTTT
TGGGGGT
TGGGGGT
MGGGGGD
TGGGGGT
TGGGGGT
THHHHHT

TTTTTTT
T55555T
T44444T
M33333D
T22222T
T11111T
THHHHHT

TTTTTTT
T55555T
T44444T
M111222
T22222T
T11111T
THHHHHT
*/

• Subtask 1: 84 / 100