Submission #1060992

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060992		SnowRaven52	Mecho (IOI09_mecho)	C++17	100 / 100	376 ms	7340 KiB

mecho

#include <bits/stdc++.h>

using namespace std;

const int maxn = 805;
int n, s, b[maxn][maxn], m[maxn][maxn];
int dr[] = {0, 0, -1, 1};
int dc[] = {-1, 1, 0, 0};
char grid[maxn][maxn];
pair<int, int> st;
vector<pair<int, int>> hives;

bool check(int r, int c){
	return 0 <= r && r < n && 0 <= c && c < n;
}

bool ok(int t){
	memset(b, -1, sizeof b);
	memset(m, -1, sizeof m);
	queue<pair<int, int>> q;
	for(auto x: hives){
		q.push(x);
		b[x.first][x.second] = 0;
	}
	while(!q.empty()){
		auto[r, c] = q.front();
		if(b[r][c]==t) break;
		q.pop();
		for(int i = 0; i < 4; i++){
			int r2 = r + dr[i];
			int c2 = c + dc[i];
			if(check(r2, c2) && (grid[r2][c2] == 'M' || grid[r2][c2]=='G')&&b[r2][c2]==-1){
				b[r2][c2] = b[r][c] + 1;
				q.emplace(r2, c2);
			}
		}
	}

	queue<pair<int, int>> pos_loc;
	pos_loc.push(st);
	m[st.first][st.second] = 0;
	int t2 = t;
	while(!pos_loc.empty()){
		t2++;
		while(!pos_loc.empty()){
			auto[r, c] = pos_loc.front();
			if(m[r][c]==(t2-t)*s)
				break;
			pos_loc.pop();
			if(~b[r][c]) continue;
			for(int i = 0; i < 4; i++){
				int r2 = r + dr[i];
				int c2 = c + dc[i];
				if(check(r2, c2) && b[r2][c2] == -1 && m[r2][c2] == -1 && (grid[r2][c2] == 'G' || grid[r2][c2] == 'D')){
					if(grid[r2][c2]=='D') return true;
					m[r2][c2] = m[r][c] + 1;
					pos_loc.emplace(r2, c2);
				}
			}
		}
		while(!q.empty()){
			auto[r, c] = q.front();
			if(b[r][c] == t2)break;
			q.pop();
			for(int i = 0; i < 4; i++){
				int r2 = r + dr[i];
				int c2 = c + dc[i];
				if(check(r2, c2) && b[r2][c2] == -1 && (grid[r2][c2] == 'G' || grid[r2][c2] == 'M')){
					b[r2][c2] = b[r][c] + 1;
					q.emplace(r2, c2);
				}
			}
		}
	}
	return false;
}

int main() {
	ios::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];
			if(grid[i][j]=='M') st = {i, j};
			else if(grid[i][j]=='H') hives.push_back(make_pair(i, j));
		}
	int ans = -1;
	for(int u = int(1e6); u > 0; u /= 2) while(ans + u <= int(1e6) && ok(ans + u)) ans += u;
	cout << ans;
}

• Subtask 1: 100 / 100