Submission #113163

#	Time	Username	Problem	Language	Result	Execution time	Memory
113163		joseacaz	Mecho (IOI09_mecho)	C++17	100 / 100	342 ms	12992 KiB

mecho

#include <iostream>
#include <queue>
#define MAXN 805
#define INF (1LL << 40LL)
#define pii pair < lld, lld >
#define mp make_pair

using namespace std;
typedef long long lld;

lld N, S, bees[MAXN][MAXN], answer[MAXN][MAXN], Mx, My, x, y, s, e, mid, ans, ansX, ansY;
bool visited[MAXN][MAXN], val;
char forest[MAXN][MAXN];
pii aux;
queue < pii > Q;
lld dx[] = {1, -1, 0, 0};
lld dy[] = {0, 0, 1, -1};

bool valid ( lld _x, lld _y )
{
	if ( _x < 0 || _x >= N )
		return false;
	if ( _y < 0 || _y >= N )
		return false;
	if ( visited[_x][_y] || forest[_x][_y] == 'T' || forest[_x][_y] == 'D')
		return false;

	return true;
}

bool valid2 ( lld _x, lld _y )
{
	if ( _x < 0 || _x >= N )
		return false;
	if ( _y < 0 || _y >= N )
		return false;

	return true;
}

bool validM ( lld _x, lld _y )
{
	if ( _x < 0 || _x >= N )
		return false;
	if ( _y < 0 || _y >= N )
		return false;
	if ( visited[_x][_y] || forest[_x][_y] == 'T')
		return false;

	return true;
}

bool solve ( lld v )
{
	for ( lld i = 0; i < N; i++ )
		for ( lld j = 0; j < N; j++ )
			answer[i][j] = INF, visited[i][j] = 0;
	
	while ( !Q.empty() )
		Q.pop();

	Q.push ( mp ( Mx, My ) );
	answer[Mx][My] = S * v;

	while ( !Q.empty() )
	{
		aux = Q.front();
		Q.pop();

		x = aux.first;
		y = aux.second;

		if ( x == ansX && y == ansY )
			return true;

		if ( answer[x][y] < bees[x][y] )
		{
			for ( lld i = 0; i < 4; i++ )
			{
				if ( validM ( x + dx[i], y + dy[i] ) )
				{
					Q.push ( mp ( x + dx[i], y + dy[i] ) );
					answer[x + dx[i]][y + dy[i]] = answer[x][y] + 1;
					visited[x + dx[i]][y + dy[i]] = 1;
				}
			}
		}
	}
	return false;
}

int main ()
{
	cin >> N >> S;
	for ( lld i = 0; i < N; i++ )
	{
		for ( lld j = 0; j < N; j++ )
		{
			bees[i][j] = INF;
			cin >> forest[i][j];
			if ( forest[i][j] == 'H' )
			{
				Q.push ( mp ( i, j ) );
				bees[i][j] = 0;
				visited[i][j] = 1;
			}

			if ( forest[i][j] == 'M' )
				Mx = i, My = j;

			if ( forest[i][j] == 'D' )
				ansX = i, ansY = j;
		}
	}

	while ( !Q.empty() )
	{
		aux = Q.front();
		Q.pop();

		x = aux.first;
		y = aux.second;

		for ( lld i = 0; i < 4; i++ )
		{
			if ( valid ( x + dx[i], y + dy[i] ) )
			{
				Q.push ( mp ( x + dx[i], y + dy[i] ) );
				bees[x + dx[i]][y + dy[i]] = bees[x][y] + S;
				visited[x + dx[i]][y + dy[i]] = 1;
			}
		}
	}

	ans = -1;
	s = 0, e = (1<<20);
	while ( s <= e )
	{
		mid = (s + e) / 2;
		val = solve ( mid );

		if ( val )
		{
			ans = mid;
			s = mid + 1;
		}
		else
			e = mid - 1;
	}

	cout << ans << "\n";

	return 0;
}

• Subtask 1: 100 / 100