Submission #1185266

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185266		prism7k	Mecho (IOI09_mecho)	C++20	13 / 100	184 ms	6616 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>> q1, q2;
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < n; ++j) {
			cin >> grid[i][j];
			if(grid[i][j] == 'M') {
				q1.push({i, j});
				bear_dist[i][j] = 0;
				bear_start = {i, j};
			} else if(grid[i][j] == 'H') {
				q2.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(!q1.empty()) {
		int cy = q1.front().first, cx = q1.front().second;
		q1.pop();
		
		for(auto dir : dirs) {
			int dy = cy + dir.first;
			int dx = cx + dir.second;
			if(!valid(dy, dx) || bear_dist[dy][dx] != INF) continue;
			bear_dist[dy][dx] = bear_dist[cy][cx] + 1;
			q1.push({dy, dx});
		}
	}
	while(!q2.empty()) {
		int cy = q2.front().first, cx = q2.front().second;
		q2.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;
			q2.push({dy, dx});
		}
	}
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < n; ++j) {
			if(bear_dist[i][j] == INF) continue;
			bear_dist[i][j] = ceil(bear_dist[i][j] / (double)s);
		}
	}
	function<void(int, int, int)> repl = [&](int y, int x, int cr) {
		if (visited[y][x]) return;
		if(cr > s) return;
		visited[y][x] = true;
		bear_dist[y][x] = 0;
		for(auto dir : dirs) {
			int dy = y + dir.first;
			int dx = x + dir.second;
			if(!valid(dy, dx)) continue;
			repl(dy, dx, cr + 1);
		}
	};
	repl(end.first, end.second, 0);
	function<bool(int)> possible = [&](int val) {
		int sy = bear_start.first, sx = bear_start.second; 
		if(bear_dist[sy][sx] + val >= bee_dist[sy][sx]) return false;
		
		vector<vector<bool>> vis(n, vector<bool>(n));
		queue<pair<int, int>> q3;
		bool pos = false;
		q3.push({sy, sx});
		vis[sy][sx] = true;
		while(!q3.empty()) {
			int cy = q3.front().first, cx = q3.front().second;
			q3.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) && !vis[dy][dx] && bear_dist[dy][dx] + val < bee_dist[dy][dx]) {
					vis[dy][dx] = true;
					q3.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: 13 / 100