Submission #100602

#	Time	Username	Problem	Language	Result	Execution time	Memory
100602		luciocf	Mecho (IOI09_mecho)	C++14	100 / 100	218 ms	5112 KiB

mecho

// IOI 2009 - Mecho
// Lúcio Cardoso

#include <bits/stdc++.h>

using namespace std;

const int maxn = 810;

typedef pair<int, int> pii;

int n, s, ox, oy, dx, dy;
int dist[maxn][maxn];

char tab[maxn][maxn];

bool mark[maxn][maxn];

int linha[] = {-1, 1, 0, 0};
int coluna[] = {0, 0, -1, 1};

void bfs(void)
{
	queue<pii> fila;

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			if (tab[i][j] == 'H')
				dist[i][j] = 0, fila.push({i, j});

	dist[dx][dy] = 1e9+10;

	while (!fila.empty())
	{
		int x = fila.front().first, y = fila.front().second;
		fila.pop();

		for (int i = 0; i < 4; i++)
		{
			int a = x+linha[i], b = y+coluna[i];
			if (a < 1 || a > n || b < 1 || b > n || tab[a][b] == 'T' || tab[a][b] == 'D' || dist[a][b] != -1) continue;

			dist[a][b] = dist[x][y] + s;
			fila.push({a, b});
		}
	}
}

bool ok(int t)
{
	if (t*s >= dist[ox][oy]) return false;

	queue<pair<int, pii> > fila;

	memset(mark, 0, sizeof mark);

	mark[ox][oy] = 1;
	fila.push({t*s, {ox, oy}});

	while (!fila.empty())
	{
		int d = fila.front().first;
		int x = fila.front().second.first, y = fila.front().second.second;
		fila.pop();

		for (int i = 0; i < 4; i++)
		{
			int a = x+linha[i], b = y+coluna[i];
			if (a < 1 || a > n || b < 1 || b > n || tab[a][b] == 'T' || d+1 >= dist[a][b] || mark[a][b]) continue;

			if (tab[a][b] == 'D') return true;

			mark[a][b] = 1;
			fila.push({d+1, {a, b}});
		}
	}

	return false;
}

int busca(void)
{
	int ini = 0, fim = 640000*2, ans = -1;

	while (ini <= fim)
	{
		int mid = (ini+fim)>>1;

		if (ok(mid)) ini = mid+1, ans = mid;
		else fim = mid-1;
	}

	return ans;
}

int main(void)
{
	cin >> n >> s;

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			cin >> tab[i][j];

			if (tab[i][j] == 'M') ox = i, oy = j;
			if (tab[i][j] == 'D') dx = i, dy = j;
		}
	}

	memset(dist, -1, sizeof dist);
	bfs();

	cout << busca() << "\n";
}

• Subtask 1: 100 / 100