Submission #1121282

#	Time	Username	Problem	Language	Result	Execution time	Memory
1121282		buzdi	Mecho (IOI09_mecho)	C++17	57 / 100	123 ms	7240 KiB

mecho

#include <iostream>
#include <cassert>
#include <cstring>
#include <queue>
#define ll long long

using namespace std;

const int NMAX = 800;
const int di[] = { 0, 0, 1, -1 };
const int dj[] = { 1, -1, 0, 0 };

struct Triplet {
	int i, j, k;
};

int n, s, istart, jstart, ifinal, jfinal;
char a[NMAX + 1][NMAX + 1];
int dh[NMAX + 1][NMAX + 1], d[NMAX + 1][NMAX + 1];
queue<pair<int, int>> qh;

bool InMat(int i, int j) {
	return i >= 1 && i <= n && j >= 1 && j <= n;
}

void BFS_hives(queue<pair<int, int>>& q) {
	while (!q.empty()) {
		auto [i, j] = q.front();
		q.pop();

		for(int d = 0; d < 4; d++) {
			int inou = i + di[d];
			int jnou = j + dj[d];
			if (InMat(inou, jnou) && (a[inou][jnou] == 'G' || a[inou][jnou] == 'M') && dh[inou][jnou] == -1) {
				dh[inou][jnou] = dh[i][j] + 1;
				q.push({ inou, jnou });
			}
		}
	}
}

void BFS(int istart, int jstart, int t) {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			d[i][j] = -1;
		}
	}
	
	if (dh[istart][jstart] != -1 && dh[istart][jstart] <= t) {
		return;
	}

	queue<Triplet> q;
	d[istart][jstart] = t;
	q.push({ istart, jstart, s });
	while (!q.empty()) {
		auto [i, j, k] = q.front();
		q.pop();

		for (int dir = 0; dir < 4; dir++) {
			int inou = i + di[dir];
			int jnou = j + dj[dir];
			if (InMat(inou, jnou) && a[inou][jnou] != 'T' && d[inou][jnou] == -1) {
				int nxt_d = d[i][j] + (k == s ? 1 : 0);
				if (dh[inou][jnou] == -1 || nxt_d <= dh[inou][jnou] - (k + 1 == s && a[inou][jnou] != 'D')) {
					d[inou][jnou] = nxt_d;
					q.push({ inou, jnou, (k == s ? 1 : k + 1)});
				}
			}
		}
	}
}

void Print(int d[NMAX + 1][NMAX + 1]) {
	for (int i = 1; i <= n; i++, cout << '\n') {
		for (int j = 1; j <= n; j++) {
			cout << d[i][j] << ' ';
		}
	}
	cout << '\n';
}

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

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

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			dh[i][j] = -1;
		}
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (a[i][j] == 'M') {
				istart = i;
				jstart = j;
			}
			else if (a[i][j] == 'D') {
				ifinal = i;
				jfinal = j;
			}
			else if (a[i][j] == 'H') {
				dh[i][j] = 0;
				qh.push({ i, j });
			}
		}
	}

	BFS_hives(qh);
	
	int left = 0, right = 1e9, answer = -1;
	while (left <= right) {
		int mid = (left + right) / 2;
		BFS(istart, jstart, mid);
		if (d[ifinal][jfinal] != -1) {
			answer = mid;
			left = mid + 1;
		}
		else {
			right = mid - 1;
		}
	}
	cout << answer << '\n';

	return 0;
}

• Subtask 1: 57 / 100