Submission #1185772

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185772		prism7k	Mecho (IOI09_mecho)	C++20	100 / 100	181 ms	6312 KiB

mecho

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

char grid[800][800];
int bee_dist[800][800];
int bear_dist[800][800];
bool visited[800][800];
const int INF = 2e9+5;

vector<pair<int, int>> dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

int main() {
	pair<int, int> bear_start;
	pair<int, int> end;
	for(int i = 0; i < 800; ++i) {
		for(int j = 0; j < 800; ++j) {
			bee_dist[i][j] = bear_dist[i][j] = INF;
		}
	}
	int n, s; cin >> n >> s;
	queue<pair<int, int>> q;
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < n; ++j) {
			cin >> grid[i][j];
			if(grid[i][j] == 'M') {
				bear_start = {i, j};
			} else if(grid[i][j] == 'H') {
				q.push({i, j});
				bee_dist[i][j] = 0;
			} else if(grid[i][j] == 'D') {
				end = {i, j};
			}
		}
	}
	function<bool(int, int)> valid = [&](int y, int x) {
		return (y >= 0 && y < n && x >= 0 && x < n && grid[y][x] != 'T');
	};
	while(!q.empty()) {
		int cy = q.front().first, cx = q.front().second;
		q.pop();
		
		for(auto dir : dirs) {
			int dy = cy + dir.first;
			int dx = cx + dir.second;
			if(!valid(dy, dx) || bee_dist[dy][dx] != INF || grid[dy][dx] == 'D') continue;
			bee_dist[dy][dx] = bee_dist[cy][cx] + 1;
			q.push({dy, dx});
		}
	}
	function<void()> reset = [&]() {
		for(int i = 0; i < n; ++i) {
			for(int j = 0; j < n; ++j) {
				bear_dist[i][j] = INF;
			}
		}
	};
	function<bool(int)> possible = [&](int val) {
		int sy = bear_start.first, sx = bear_start.second;
		reset();
		bear_dist[sy][sx] = 0;
		if(bear_dist[sy][sx] + val >= bee_dist[sy][sx]) return false;
		
		queue<pair<int, int>> qb;
		bool pos = false;
		qb.push({sy, sx});
		
		while(!qb.empty()) {
			int cy = qb.front().first, cx = qb.front().second;
			qb.pop();
			if(grid[cy][cx] == 'D') {
				pos = true;
				break;
			}
			for(auto dir : dirs) {
				int dy = cy + dir.first;
				int dx = cx + dir.second;
				if(
					valid(dy, dx) && 
					bear_dist[dy][dx] == INF &&
					((bear_dist[cy][cx] + 1) / s + val) < bee_dist[dy][dx]
				  ) {
					bear_dist[dy][dx] = bear_dist[cy][cx] + 1;
					qb.push({dy, dx});
				}
			}
		}
		return pos;
	};
	int l = 0, r = 1'000'000, best = -1;
	while(l < r) {
		int mid = l + (r - l) / 2;
		if(possible(mid)) {
			best = mid;
			l = mid + 1;
		} else {
			r = mid;
		}
	}
	cout << best << "\n";
}
	

• Subtask 1: 100 / 100