Submission #1193042

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193042		alexscrip	Mecho (IOI09_mecho)	C++20	100 / 100	155 ms	6236 KiB

mecho

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

int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n, s; cin >> n >> s;
	
	vector<string> grid(n);
	for (int i = 0; i < n; i++) cin >> grid[i];
	
	vector<vector<int>> bee_time(n, vector<int>(n, INT_MAX));
	
	
	int hx, hy;
	int hpx, hpy;
	
	queue<pair<int, int>> b;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (grid[i][j] == 'H') {
				bee_time[i][j] = 0;
				b.push({i, j});
			} else if (grid[i][j] == 'M') {
				hpx = i; hpy = j;
			} else if (grid[i][j] == 'D') {
				hx = i, hy = j;
			}
		}
	}
	
	// Bee time BFS
	
	while (!b.empty()) {
		int x = b.front().first, y = b.front().second;
		b.pop();
		
		for (int i = 0; i < 4; i++) {
			int nx = dx[i] + x, ny = dy[i] + y;
			
			if (nx >= 0 && nx < n && ny >= 0 && ny < n && bee_time[nx][ny] == INT_MAX && (grid[nx][ny] == 'G' || grid[nx][ny] == 'M')) {
				bee_time[nx][ny] = bee_time[x][y] + 1;
				b.push({nx, ny});
			}
		}
	}
	
	int l = 0, r = n * n;
	int ans = -1;
	
	while (l <= r) {
		int mid = l + (r - l) / 2;
		
		int valid = 0;
		
		vector<vector<int>> steps(n, vector<int>(n, INT_MAX));
		queue<pair<int,int>> q;
		
		q.push({hpx, hpy});
		steps[hpx][hpy] = 0;
		if (bee_time[hpx][hpy] == INT_MAX || bee_time[hpx][hpy] <= mid) {
			q.pop();
		}
	
		while (!q.empty()) {
			int x = q.front().first, y = q.front().second;
			q.pop();
			
			for (int i = 0; i < 4; i++) {
				int nx = dx[i] + x, ny = dy[i] + y;
				
				if (nx >= 0 && nx < n && ny >= 0 && ny < n && (grid[nx][ny] == 'G' || grid[nx][ny] == 'D') && steps[nx][ny] == INT_MAX) {
					if (bee_time[nx][ny] == INT_MAX || ((steps[x][y] + 1) / s) < bee_time[nx][ny] - mid) {
						if (grid[nx][ny] == 'D') {
							valid = 1;
							break;
						}
						steps[nx][ny] = steps[x][y] + 1;
						q.push({nx, ny});
					}
				}
			}
			
		}
		
		// check if adjacent cell to the home is visitable
		
		if (valid) {
			ans = mid;
			l = mid + 1;
		} else r = mid - 1;
	}
	
	cout << ans << '\n';
	
	return 0;
}
			
		

• Subtask 1: 100 / 100