제출 #586784

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
586784		Drew_	Mecho (IOI09_mecho)	C++17	100 / 100	332 ms	4812 KiB

mecho

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define f1 first
#define s2 second

using ii = pair<int, int>;

const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
const int MAX = 869;
const int inf = 1e9 + 69;

int N, S;
char s[MAX][MAX];
int dist[MAX][MAX];

inline bool valid(int r, int c)
{
	return 0 <= r && r <= N && 0 <= c && c < N;
}

int main()
{
	ios :: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> N >> S;
	for (int i = 0; i < N; ++i)
		cin >> s[i];

	ii st, fn;
	vector<ii> bee;

	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			if (s[i][j] == 'M')
				st = {i, j};
			else if (s[i][j] == 'H')
				bee.pb({i, j});
			else if (s[i][j] == 'D')
				fn = {i, j};
		}
	}


	const auto check = [&](int val) -> bool
	{
		queue<ii> q, qb; //bear, bee
		for (int i = 0; i < N; ++i)
			for (int j = 0; j < N; ++j)
				dist[i][j] = -inf;

		const auto bearMove = [&]() -> bool
		{
			while (!q.empty() && dist[q.front().f1][q.front().s2] < 0)
				q.pop();
			if (q.empty())
				return false;

			bool moved = false;
			int cur = dist[q.front().f1][q.front().s2];
			while (!q.empty())
			{
				auto [r, c] = q.front();
				if (dist[r][c] >= cur + S)
					break;

				q.pop();
				if (dist[r][c] < 0)
					continue;
				

				for (int i = 0; i < 4; ++i)
				{
					int nr = r + dx[i], nc = c + dy[i];
					if (valid(nr, nc) && s[nr][nc] != 'T' && (dist[nr][nc] == -inf))
						moved = true, dist[nr][nc] = dist[r][c] + 1, q.push({nr, nc}); 
				}
			}

			return moved;
		};

		const auto beeSwarm = [&]() -> void
		{
			if (qb.empty())
				return;

			int cur = dist[qb.front().f1][qb.front().s2];
			while (!qb.empty())
			{
				auto [r, c] = qb.front();
				if (dist[r][c] != cur)
					break;
				qb.pop();

				for (int i = 0; i < 4; ++i)
				{
					int nr = r + dx[i], nc = c + dy[i];
					if (valid(nr, nc) && s[nr][nc] != 'T' && s[nr][nc] != 'D' && (dist[nr][nc] == -inf || dist[nr][nc] >= 0))
						dist[nr][nc] = dist[r][c] - 1, qb.push({nr, nc});
				}
			}
		};

		dist[st.f1][st.s2] = 0;
		q.push(st);

		for (auto [r, c] : bee)
			dist[r][c] = -1, qb.push({r, c});

		for (int rep = 0; rep < val; ++rep)
			beeSwarm();

		while (dist[fn.f1][fn.s2] == -inf)
		{
			if (!bearMove())
				return false;
			beeSwarm();

			// for (int i = 0; i < N; ++i)
			// 	for (int j = 0; j < N; ++j)
			// 		cerr << setw(2) << max(-9, dist[i][j]) << " \n"[j == N-1];
		}

		return true;
	};

	int l = -1, r = N*N;
	while (l < r)
	{
		int mid = (l + r + 1) >> 1;
		if (check(mid)) l = mid;
		else r = mid - 1;
	}

	cout << l << '\n';
	return 0;
}

• Subtask 1: 100 / 100