Submission #716336

#	Time	Username	Problem	Language	Result	Execution time	Memory
716336		yashsingh	Mecho (IOI09_mecho)	C++17	95 / 100	197 ms	6076 KiB

mecho

#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> pii;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, s;
	cin >> n >> s;

	vector<vector<char>> grid(n, vector<char>(n));
	
	pii start, end;
	for (int i{0}; i < n; ++i) {
		for (int j{0}; j < n; ++j) {
			cin >> grid[i][j];
			if (grid[i][j] == 'M') start = {i,j};
			else if (grid[i][j] == 'D') end = {i,j};
		}
	}

	queue<pair<int,int>> q;
	vector<vector<int>> pollu(n, vector<int>(n, INT_MAX));
	for (int i{0}; i < n; ++i) {
		for (int j{0}; j < n; ++j) {
			if (grid[i][j] == 'H') {
				pollu[i][j] = 0;
				q.push({i, j});
			}
		}
	}

	// precompute distance to pollinate all regions
	int dx[4] {-1, 1, 0, 0};
	int dy[4] {0, 0, 1, -1};
	while (q.size()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i{0}; i < 4; ++i) {
			if (x + dx[i] < 0 || x + dx[i] >= n || y + dy[i] < 0 || y + dy[i] >= n || grid[x + dx[i]][y + dy[i]] == 'T') {
				continue;
			}
			if (pollu[x][y] + 1 < pollu[x + dx[i]][y + dy[i]]) {
				pollu[x + dx[i]][y + dy[i]] = pollu[x][y] + 1;
				q.push({x + dx[i], y + dy[i]});
			}
		}
	}

	// for (int i{0}; i < n; ++i) {
	// 	for (int j{0}; j < n; ++j) {
	// 		if (pollu[i][j] == INT_MAX) {
	// 			cout << '-' << ' ';
	// 			continue;
	// 		}
	// 		cout << pollu[i][j] << ' ';
	// 	}
	// 	cout << '\n';
	// }

	// we can tell by construction that any adjacent cell will have either +1 or -1, we want to move on +1 route
	// similarly we can tell that a movement of s cells is +[0,s]
	// we want to find a maximum min over all segments of size s
	// we can start by precomputing the distance to each cell from M

	vector<vector<int>> dist(n, vector<int>(n, INT_MAX));

	// implement binary search with bfs
	// can't precompute distances, they are dependent on bee timings
	int l{0}, r{n*n}, ans{-1};
	while (l <= r) {
		int mid{(l+r)/2};
		q.push(start);
		for (int i{0}; i < n; ++i) {
			for (int j{0}; j < n; ++j) {
				dist[i][j] = INT_MAX;
			}
		}
		dist[start.first][start.second] = 0;
		while (q.size()) {
			int x = q.front().first;
			int y = q.front().second;
			q.pop();
			for (int i{0}; i < 4; ++i) {
				if (x + dx[i] < 0 || x + dx[i] >= n || y + dy[i] < 0 || y + dy[i] >= n) continue;
				if (grid[x + dx[i]][y + dy[i]] == 'T') continue;
				if (pollu[x][y]-mid > (dist[x][y])/s && dist[x][y] + 1 < dist[x + dx[i]][y + dy[i]]) {
					dist[x + dx[i]][y + dy[i]] = dist[x][y] + 1;
					q.push({x + dx[i], y + dy[i]});
				}
			}
		}
		// cout << mid << '\n';
		// for (int i{0}; i < n; ++i) {
		// 	for (int j{0}; j < n; ++j) {
		// 		if (dist[i][j] == INT_MAX) {
		// 			cout << '-' << ' ';
		// 			continue;
		// 		}
		// 		cout << dist[i][j] << ' ';
		// 	}
		// 	cout << '\n';
		// }
		if (dist[end.first][end.second] == INT_MAX) {
			r = mid-1;
		} else {
			l = mid+1;
			ans = mid;
		}
	}

	cout << ans << "\n";

  return 0;
}

• Subtask 1: 95 / 100