oj.uz

Submission #515847

# Submission time Handle Problem Language Result Execution time Memory
515847 2022-01-19T23:48:16 Z Tizariox Mecho (IOI09_mecho) C++14
73 / 100
 1000 ms 47988 KB 
#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();
	FOR(i, 0, sz) {
		pii node = beeQueue.front();
		beeQueue.pop();
		for (pii neighbor : adj[node.pA][node.pB]) {
			if (!visBee[neighbor.pA][neighbor.pB] && !(neighbor.pA == homeX && neighbor.pB == homeY)) {
				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;
}

Subtask #1
73.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 15312 KB Output is correct
2 Correct 13 ms 15308 KB Output is correct
3 Correct 15 ms 15308 KB Output is correct
4 Correct 15 ms 15380 KB Output is correct
5 Correct 12 ms 15308 KB Output is correct
6 Correct 12 ms 15392 KB Output is correct
7 Execution timed out 1071 ms 47840 KB Time limit exceeded
8 Correct 12 ms 15308 KB Output is correct
9 Correct 15 ms 15412 KB Output is correct
10 Correct 12 ms 15340 KB Output is correct
11 Correct 12 ms 15308 KB Output is correct
12 Correct 13 ms 15564 KB Output is correct
13 Correct 18 ms 15560 KB Output is correct
14 Correct 14 ms 15564 KB Output is correct
15 Correct 12 ms 15400 KB Output is correct
16 Correct 12 ms 15308 KB Output is correct
17 Correct 12 ms 15308 KB Output is correct
18 Correct 12 ms 15424 KB Output is correct
19 Correct 13 ms 15352 KB Output is correct
20 Correct 12 ms 15436 KB Output is correct
21 Correct 12 ms 15488 KB Output is correct
22 Correct 13 ms 15436 KB Output is correct
23 Correct 12 ms 15404 KB Output is correct
24 Correct 12 ms 15480 KB Output is correct
25 Correct 13 ms 15436 KB Output is correct
26 Correct 13 ms 15564 KB Output is correct
27 Correct 13 ms 15564 KB Output is correct
28 Correct 14 ms 15564 KB Output is correct
29 Correct 14 ms 15480 KB Output is correct
30 Correct 14 ms 15564 KB Output is correct
31 Correct 16 ms 15612 KB Output is correct
32 Correct 13 ms 15564 KB Output is correct
33 Correct 36 ms 18160 KB Output is correct
34 Correct 37 ms 18128 KB Output is correct
35 Correct 114 ms 20084 KB Output is correct
36 Correct 47 ms 18960 KB Output is correct
37 Correct 46 ms 18884 KB Output is correct
38 Correct 193 ms 21436 KB Output is correct
39 Correct 54 ms 19680 KB Output is correct
40 Correct 54 ms 19712 KB Output is correct
41 Correct 270 ms 22912 KB Output is correct
42 Correct 70 ms 20704 KB Output is correct
43 Correct 65 ms 20676 KB Output is correct
44 Correct 346 ms 24560 KB Output is correct
45 Correct 86 ms 21700 KB Output is correct
46 Correct 79 ms 21628 KB Output is correct
47 Correct 430 ms 26364 KB Output is correct
48 Correct 101 ms 22680 KB Output is correct
49 Correct 91 ms 22768 KB Output is correct
50 Correct 514 ms 28344 KB Output is correct
51 Correct 112 ms 23940 KB Output is correct
52 Correct 102 ms 23920 KB Output is correct
53 Correct 631 ms 30472 KB Output is correct
54 Correct 115 ms 25156 KB Output is correct
55 Correct 116 ms 25160 KB Output is correct
56 Correct 729 ms 32760 KB Output is correct
57 Correct 136 ms 26416 KB Output is correct
58 Correct 137 ms 26440 KB Output is correct
59 Correct 863 ms 35220 KB Output is correct
60 Correct 148 ms 27972 KB Output is correct
61 Correct 151 ms 27844 KB Output is correct
62 Execution timed out 1014 ms 37824 KB Time limit exceeded
63 Correct 564 ms 31384 KB Output is correct
64 Correct 542 ms 31380 KB Output is correct
65 Correct 552 ms 31440 KB Output is correct
66 Correct 632 ms 31388 KB Output is correct
67 Correct 539 ms 31340 KB Output is correct
68 Correct 746 ms 31464 KB Output is correct
69 Correct 680 ms 31556 KB Output is correct
70 Correct 740 ms 31552 KB Output is correct
71 Correct 681 ms 31424 KB Output is correct
72 Correct 802 ms 31420 KB Output is correct
73 Execution timed out 1043 ms 47916 KB Time limit exceeded
74 Execution timed out 1063 ms 47856 KB Time limit exceeded
75 Execution timed out 1062 ms 47916 KB Time limit exceeded
76 Execution timed out 1044 ms 47820 KB Time limit exceeded
77 Execution timed out 1074 ms 47912 KB Time limit exceeded
78 Execution timed out 1093 ms 47828 KB Time limit exceeded
79 Execution timed out 1077 ms 47812 KB Time limit exceeded
80 Execution timed out 1084 ms 47988 KB Time limit exceeded
81 Execution timed out 1056 ms 47816 KB Time limit exceeded
82 Execution timed out 1067 ms 47812 KB Time limit exceeded
83 Execution timed out 1075 ms 47752 KB Time limit exceeded
84 Execution timed out 1062 ms 47816 KB Time limit exceeded
85 Execution timed out 1071 ms 47728 KB Time limit exceeded
86 Execution timed out 1071 ms 47748 KB Time limit exceeded
87 Execution timed out 1069 ms 47764 KB Time limit exceeded
88 Execution timed out 1012 ms 47916 KB Time limit exceeded
89 Execution timed out 1075 ms 47684 KB Time limit exceeded
90 Execution timed out 1067 ms 47804 KB Time limit exceeded
91 Execution timed out 1083 ms 47724 KB Time limit exceeded
92 Execution timed out 1096 ms 47800 KB Time limit exceeded