Submission #815784

#	Time	Username	Problem	Language	Result	Execution time	Memory
815784		Mustela_Erminea	Mecho (IOI09_mecho)	C++14	89 / 100	156 ms	6548 KiB

mecho

#include <iostream>
#include <vector>
#include <queue>
#define pii pair<int, int>

using namespace std;

int N, S;
int mR, mC, dR, dC;
char grid[801][801];
int minHiveDist[801][801], minBearDist[801][801];

const int dx[4] = { -1, 1, 0, 0 };
const int dy[4] = { 0, 0, -1, 1 };
bool isValid(int r, int c) { return 0 <= r && r < N && 0 <= c && c < N; }

vector<vector<bool>> visited;
void bfs(vector<pii> initialCoords, int minDist[801][801]) {
	queue<pair<pii, int>> q; 
	visited.clear(); visited.resize(N, vector<bool>(N));
	for (pii p : initialCoords) {
		q.push({ p, 0 }); visited[p.first][p.second] = true;
	}
	while (!q.empty()) {
		pii loc = q.front().first; int dist = q.front().second; q.pop();
		minDist[loc.first][loc.second] = dist;
		for (int i = 0; i < 4; i++) {
			int r = loc.first + dx[i], c = loc.second + dy[i];
			if (isValid(r, c) && !visited[r][c] && (grid[r][c] == 'G' || grid[r][c] == 'M')) {
				visited[r][c] = true;
				q.push({ {r, c}, dist + 1 });
			}
		}
	}
}

void bfs2(int startR, int startC, int wait) {
	visited.clear(); visited.resize(N, vector<bool>(N));
	queue<pair<pii, int>> q; q.push({ {startR, startC}, 0 });
	visited[startR][startC] = true;
	while (!q.empty()) {
		pii loc = q.front().first; int dist = q.front().second; q.pop();
		minBearDist[loc.first][loc.second] = dist;
		for (int i = 0; i < 4; i++) {
			int r = loc.first + dx[i], c = loc.second + dy[i];
			if (isValid(r, c) && !visited[r][c] && (grid[r][c] == 'G' || grid[r][c] == 'M')) {
				if ((dist + 1) / S + wait < minHiveDist[r][c]) {
					visited[r][c] = true;
					q.push({ {r, c}, dist + 1 });
				}
			}
		}
	}
}
bool works(int wait) {
	bfs2(mR, mC, wait);
	for (int i = 0; i < 4; i++) {
		int r = dR + dx[i], c = dC + dy[i];
		if (isValid(r, c) && visited[r][c] && minBearDist[r][c] / S + wait < minHiveDist[r][c]) return true;
	} return false;
}

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

	cin >> N >> S;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> grid[i][j];
	
	vector<pii> hives;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (grid[i][j] == 'H') hives.push_back({ i, j });
			if (grid[i][j] == 'M') { mR = i; mC = j; }
			if (grid[i][j] == 'D') { dR = i; dC = j; }
		}
	}

	bfs(hives, minHiveDist); minHiveDist[dR][dC] = (int)1e9;

	int low = -1, high = N * N;
	while (low < high) {
		int mid = (low + high + 1) / 2;
		if (works(mid)) low = mid;
		else high = mid - 1;
	} cout << low << endl;
}

• Subtask 1: 89 / 100