Submission #514973

#	Time	Username	Problem	Language	Result	Execution time	Memory
514973		Tizariox	Mecho (IOI09_mecho)	C++14	0 / 100	1100 ms	47156 KiB

mecho

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

using ll = long long;
using pii = pair<int, int>;

#define FOR(i, a, b) for (int i = a; i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define F0R1(i, a) for (int i = 1; i <= (a); i++)
#define FORd(i, a, b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i, a) for (int i = (a)-1; i >= 0; i--)
#define F0Rd1(i, a) for (int i = a; i > 0; i--)
#define SORT(vec) sort(vec.begin(), vec.end())
#define S0RT(arr, n) sort(arr, arr + n)

#define pA first
#define pB second
#define MOD 1000000007
#define nl "\n"
#define pb push_back

int n, steps, rootX, rootY, homeX, homeY;

vector<pii> adj[800][800];
bool vis[800][800];
bool visBee[800][800];
bool blocked[800][800];
vector<pii> hives;
queue<pii> beeQueue;
int initialDist = 0;

void moveBees() {
	int sz = beeQueue.size();
	while (beeQueue.empty()) {
		pii node = beeQueue.front();
		beeQueue.pop();
		for (pii neighbor : adj[node.pA][node.pB]) {
			if (neighbor.pA == homeX && neighbor.pB == homeY) {
				continue;
			}
			if (!visBee[neighbor.pA][neighbor.pB]) {
				visBee[neighbor.pA][neighbor.pB] = true;
				beeQueue.push(neighbor);
			}
		}
	}
}

bool bfs(int eatHoney) {
	FOR(i, 0, n) {
		FOR(j, 0, n) {
			vis[i][j] = false;
			visBee[i][j] = false;
		}
	}
	queue<pii> bfsQueue;
	beeQueue = queue<pii>();
	vis[rootX][rootY] = true;
	bfsQueue.push(pii(rootX, rootY));
	for (pii i : hives) {
		visBee[i.pA][i.pB] = true;
		beeQueue.push(i);
	}
	FOR(i, 0, eatHoney) { moveBees(); }
	// somehow avoid having to replace the queue with every step
	while (!bfsQueue.empty()) {
		FOR(i, 0, steps) {
			int sz = bfsQueue.size();
			FOR(j, 0, sz) {
				pii node = bfsQueue.front();
				bfsQueue.pop();
				if (visBee[node.pA][node.pB]) {
					continue;
				}
				for (pii neighbor : adj[node.pA][node.pB]) {
					if (!vis[neighbor.pA][neighbor.pB] && !visBee[neighbor.pA][neighbor.pB]) {
						vis[neighbor.pA][neighbor.pB] = true;
						if (neighbor.pA == homeX && neighbor.pB == homeY) {
							return true;
						}
						bfsQueue.push(neighbor);
					}
				}
			}
		}
		moveBees();
	}
	return false;
}

void gridAdj() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (!blocked[i][j]) {
				if (i > 0 && !blocked[i - 1][j]) {
					adj[i][j].pb(pii(i - 1, j));
				}
				if (i < n - 1 && !blocked[i + 1][j]) {
					adj[i][j].pb(pii(i + 1, j));
				}
				if (j > 0 && !blocked[i][j - 1]) {
					adj[i][j].pb(pii(i, j - 1));
				}
				if (j < n - 1 && !blocked[i][j + 1]) {
					adj[i][j].pb(pii(i, j + 1));
				}
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> steps;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		FOR(j, 0, n) {
			if (s[j] == 'T') {
				blocked[i][j] = true;
			} else if (s[j] == 'M') {
				rootX = i;
				rootY = j;
			} else if (s[j] == 'D') {
				homeX = i;
				homeY = j;
			} else if (s[j] == 'H') {
				hives.pb(pii(i, j));
			}
		}
	}
	gridAdj();
	int l = 0;
	int r = 1e6;
	int ans = l - 1;
	while (l <= r) {
		ll mid = (r + l) / 2;
		if (bfs(mid)) {
			ans = mid;
			l = mid + 1;
		} else {
			r = mid - 1;
		}
	}
	cout << ans << nl;
}

Compilation message (stderr)

mecho.cpp: In function 'void moveBees()':
mecho.cpp:33:6: warning: unused variable 'sz' [-Wunused-variable]
   33 |  int sz = beeQueue.size();
      |      ^~

• Subtask 1: 0 / 100