Submission #1041304

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041304		ssitaram	Mecho (IOI09_mecho)	C++17	100 / 100	240 ms	5980 KiB

mecho

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

int main() {
	ios::sync_with_stdio(0);
	cin.tie(nullptr);
	int n, s; cin >> n >> s;
	vector<string> grid(n);
	queue<pair<int, int>> q;
	queue<int> qq;
	pair<int, int> start;
	for (int i = 0; i < n; ++i) {
		cin >> grid[i];
		for (int j = 0; j < n; ++j) {
			if (grid[i][j] == 'H') {
				q.push({i, j});
				qq.push(0);
			} else if (grid[i][j] == 'M') {
				start = {i, j};
			}
		}
	}
	vector<vector<int>> whenbee(n, vector<int>(n, INT32_MAX));
	while (!q.empty()) {
		pair<int, int> loc = q.front();
		int d = qq.front();
		q.pop(); qq.pop();
		if (loc.first < 0 || loc.first >= n || loc.second < 0 || loc.second >= n) continue;
		if (grid[loc.first][loc.second] == 'T' || grid[loc.first][loc.second] == 'D') continue;
		if (whenbee[loc.first][loc.second] != INT32_MAX) continue;
		whenbee[loc.first][loc.second] = d;
		q.push({loc.first - 1, loc.second});
		q.push({loc.first + 1, loc.second});
		q.push({loc.first, loc.second - 1});
		q.push({loc.first, loc.second + 1});
		for (int i = 0; i < 4; ++i) qq.push(d + 1);
	}
	auto works = [&whenbee, &n, &s, &grid, &start](int st) -> bool {
		queue<pair<int, int>> q;
		queue<int> qq;
		q.push(start);
		qq.push(st);
		vector<vector<bool>> vis(n, vector<bool>(n));
		while (!q.empty()) {
			pair<int, int> loc = q.front();
			int d = qq.front();
			q.pop(); qq.pop();
			if (loc.first < 0 || loc.first >= n || loc.second < 0 || loc.second >= n) continue;
			if ((d / s) >= whenbee[loc.first][loc.second]) continue;
			if (grid[loc.first][loc.second] == 'T') continue;
			if (vis[loc.first][loc.second]) continue;
			vis[loc.first][loc.second] = 1;
			if (grid[loc.first][loc.second] == 'D') {
				return 1;
			}
			q.push({loc.first - 1, loc.second});
			q.push({loc.first + 1, loc.second});
			q.push({loc.first, loc.second - 1});
			q.push({loc.first, loc.second + 1});
			for (int i = 0; i < 4; ++i) qq.push(d + 1);
		}
		return 0;
	};
	if (!works(0)) {
		cout << "-1\n";
		return 0;
	}
	int lo = 0, hi = n * n;
	while (lo < hi) {
		int mi = (lo + hi + 1) / 2;
		if (works(s * mi)) {
			lo = mi;
		} else {
			hi = mi - 1;
		}
	}
	cout << lo << '\n';
	return 0;
}

• Subtask 1: 100 / 100