Submission #758176

#	Time	Username	Problem	Language	Result	Execution time	Memory
758176		SanguineChameleon	Mecho (IOI09_mecho)	C++17	100 / 100	168 ms	7008 KiB

mecho

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

void just_do_it();

int main() {
	#ifdef KAMIRULEZ
		freopen("kamirulez.inp", "r", stdin);
		freopen("kamirulez.out", "w", stdout);
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	just_do_it();
	return 0;
}

const int maxn = 8e2 + 20;
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
bool grass[maxn][maxn];
int dist_h[maxn][maxn];
int dist_m[maxn][maxn];
int n, k, sx, sy, ex, ey;

bool check() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i != sx || j != sy) {
				dist_m[i][j] = -1;
			}
		}
	}
	deque<pair<int, int>> q;
	q.emplace_back(sx, sy);
	while (!q.empty()) {
		int cx = q.front().first;
		int cy = q.front().second;
		q.pop_front();
		for (int d = 0; d < 4; d++) {
			int nx = cx + dx[d];
			int ny = cy + dy[d];
			if (nx == ex && ny == ey) {
				return true;
			}
			if (dist_m[nx][ny] == -1 && dist_m[cx][cy] + 1 < dist_h[nx][ny] * k) {
				dist_m[nx][ny] = dist_m[cx][cy] + 1;
				q.emplace_back(nx, ny);
			}
		}
	}
	return false;
}

void just_do_it() {
	cin >> n >> k;
	deque<pair<int, int>> q;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			char c;
			cin >> c;
			if (c == 'G') {
				grass[i][j] = true;
			}
			if (c == 'M') {
				grass[i][j] = true;
				sx = i;
				sy = j;
			}
			if (c == 'D') {
				ex = i;
				ey = j;
			}
			if (c == 'H') {
				dist_h[i][j] = 0;
				q.emplace_back(i, j);
			}
			else {
				dist_h[i][j] = -1;
			}
		}
	}
	while (!q.empty()) {
		int cx = q.front().first;
		int cy = q.front().second;
		q.pop_front();
		for (int d = 0; d < 4; d++) {
			int nx = cx + dx[d];
			int ny = cy + dy[d];
			if (grass[nx][ny] && dist_h[nx][ny] == -1) {
				dist_h[nx][ny] = dist_h[cx][cy] + 1;
				q.emplace_back(nx, ny);
			}
		}
	}
	int res = -1;
	int lt = 0;
	int rt = dist_h[sx][sy] - 1;
	while (lt <= rt) {
		int mt = (lt + rt) / 2;
		dist_m[sx][sy] = mt * k;
		if (check()) {
			res = mt;
			lt = mt + 1;
		}
		else {
			rt = mt - 1;
		}
	}
	cout << res;
}

• Subtask 1: 100 / 100