Submission #943122

#	Time	Username	Problem	Language	Result	Execution time	Memory
943122		tkm_algorithms	Mecho (IOI09_mecho)	C++17	100 / 100	432 ms	7112 KiB

mecho

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


#define ff first
#define ss second
using pi = pair<int, int>;
using vpi = vector<pi>;

const int N = 805;
int n, s, b[N][N], m[N][N];
int dr[] = {0, 0, -1, 1};
int dc[] = {-1, 1, 0, 0};
char a[N][N];  // the grid
pi st;  // the starting position for mecho
vpi h;  // locations of all of the bee hives

bool good(int r, int c){  // is cell (r, c) within bounds?
	return 0 <= r && r < n && 0 <= c && c < n;
}

bool ok(int t){  // can the answer be t?
	memset(b, -1, sizeof b);
	memset(m, -1, sizeof m);
	queue<pi> q;  // all of the current bees' possible locations
	for(auto x: h){
		q.push(x);
		b[x.ff][x.ss] = 0;
	}

	// the bees "expand" for t seconds
	while(!q.empty()){  // bfs
		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(good(r2, c2)&&(a[r2][c2]=='M'||a[r2][c2]=='G')&&b[r2][c2]==-1){
				b[r2][c2] = b[r][c] + 1;
				q.emplace(r2, c2);
			}
		}
	}

	queue<pi> q2;  // mecho's possible locations
	q2.push(st);
	m[st.ff][st.ss] = 0;
	int t2 = t;
	while(!q2.empty()){
		t2++;

		// mecho's possible locations "expand" for 1 second (where he can take up to s steps)
		while(!q2.empty()){ // bfs
			auto[r, c] = q2.front();
			if(m[r][c]==(t2-t)*s)
				break;
			q2.pop();
			if(~b[r][c])
				continue;
			for(int i = 0; i < 4; ++i){
				int r2 = r + dr[i];
				int c2 = c + dc[i];
				if(good(r2, c2)&&b[r2][c2]==-1&&m[r2][c2]==-1&&
						(a[r2][c2]=='G'||a[r2][c2]=='D')){
					if(a[r2][c2]=='D')  // did mecho just find home??
						return true;  // success!
					m[r2][c2] = m[r][c] + 1;
					q2.emplace(r2, c2);
				}
			}
		}

		// the bees' possible locations "expand" by 1 second
		while(!q.empty()){  // bfs
			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(good(r2, c2)&&b[r2][c2]==-1&&(a[r2][c2]=='G'||a[r2][c2]=='M')){
					b[r2][c2] = b[r][c] + 1;
					q.emplace(r2, c2);
				}
			}
		}
	}
	return false;  // mecho never found home without encountering bees :(
}

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 >> a[i][j];
			if(a[i][j]=='M')
				st = {i, j};
			else if(a[i][j]=='H')
				h.emplace_back(i, j);
		}

	// binary search (yes this binary search might not be commonly seen, but it's shorter to write)
	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