oj.uz

답안 #514973

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
514973 2022-01-19T00:00:46 Z Tizariox Mecho (IOI09_mecho) C++14
0 / 100
 1000 ms 47156 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();
	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

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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 61 ms 15348 KB Output isn't correct
2 Incorrect 61 ms 15368 KB Output isn't correct
3 Incorrect 61 ms 15340 KB Output isn't correct
4 Incorrect 78 ms 15348 KB Output isn't correct
5 Incorrect 61 ms 15356 KB Output isn't correct
6 Incorrect 65 ms 15308 KB Output isn't correct
7 Execution timed out 1094 ms 47156 KB Time limit exceeded
8 Incorrect 59 ms 15308 KB Output isn't correct
9 Incorrect 60 ms 15376 KB Output isn't correct
10 Incorrect 59 ms 15308 KB Output isn't correct
11 Incorrect 59 ms 15308 KB Output isn't correct
12 Incorrect 59 ms 15540 KB Output isn't correct
13 Incorrect 65 ms 15564 KB Output isn't correct
14 Incorrect 62 ms 15540 KB Output isn't correct
15 Incorrect 62 ms 15392 KB Output isn't correct
16 Incorrect 59 ms 15308 KB Output isn't correct
17 Incorrect 60 ms 15400 KB Output isn't correct
18 Incorrect 60 ms 15408 KB Output isn't correct
19 Incorrect 59 ms 15436 KB Output isn't correct
20 Incorrect 59 ms 15428 KB Output isn't correct
21 Incorrect 60 ms 15460 KB Output isn't correct
22 Incorrect 59 ms 15464 KB Output isn't correct
23 Incorrect 73 ms 15392 KB Output isn't correct
24 Incorrect 61 ms 15436 KB Output isn't correct
25 Incorrect 63 ms 15540 KB Output isn't correct
26 Incorrect 71 ms 15540 KB Output isn't correct
27 Incorrect 60 ms 15564 KB Output isn't correct
28 Incorrect 60 ms 15564 KB Output isn't correct
29 Incorrect 60 ms 15584 KB Output isn't correct
30 Incorrect 60 ms 15580 KB Output isn't correct
31 Incorrect 62 ms 15564 KB Output isn't correct
32 Incorrect 60 ms 15564 KB Output isn't correct
33 Incorrect 65 ms 18088 KB Output isn't correct
34 Incorrect 66 ms 18032 KB Output isn't correct
35 Incorrect 118 ms 20044 KB Output isn't correct
36 Incorrect 69 ms 18796 KB Output isn't correct
37 Incorrect 77 ms 18792 KB Output isn't correct
38 Incorrect 140 ms 21208 KB Output isn't correct
39 Incorrect 69 ms 19596 KB Output isn't correct
40 Incorrect 70 ms 19540 KB Output isn't correct
41 Incorrect 186 ms 22708 KB Output isn't correct
42 Incorrect 72 ms 20556 KB Output isn't correct
43 Incorrect 73 ms 20444 KB Output isn't correct
44 Incorrect 258 ms 24304 KB Output isn't correct
45 Incorrect 81 ms 21392 KB Output isn't correct
46 Incorrect 73 ms 21404 KB Output isn't correct
47 Incorrect 302 ms 26068 KB Output isn't correct
48 Incorrect 76 ms 22348 KB Output isn't correct
49 Incorrect 79 ms 22412 KB Output isn't correct
50 Incorrect 363 ms 27884 KB Output isn't correct
51 Incorrect 80 ms 23512 KB Output isn't correct
52 Incorrect 79 ms 23508 KB Output isn't correct
53 Incorrect 434 ms 30064 KB Output isn't correct
54 Incorrect 82 ms 24564 KB Output isn't correct
55 Incorrect 84 ms 24684 KB Output isn't correct
56 Incorrect 483 ms 32280 KB Output isn't correct
57 Incorrect 85 ms 25924 KB Output isn't correct
58 Incorrect 88 ms 25864 KB Output isn't correct
59 Incorrect 573 ms 34668 KB Output isn't correct
60 Incorrect 93 ms 27228 KB Output isn't correct
61 Incorrect 95 ms 27204 KB Output isn't correct
62 Incorrect 640 ms 37184 KB Output isn't correct
63 Incorrect 678 ms 30764 KB Output isn't correct
64 Incorrect 660 ms 30720 KB Output isn't correct
65 Incorrect 671 ms 30780 KB Output isn't correct
66 Incorrect 678 ms 30764 KB Output isn't correct
67 Incorrect 675 ms 30768 KB Output isn't correct
68 Incorrect 665 ms 30772 KB Output isn't correct
69 Incorrect 665 ms 30732 KB Output isn't correct
70 Incorrect 664 ms 30772 KB Output isn't correct
71 Incorrect 674 ms 30768 KB Output isn't correct
72 Incorrect 117 ms 30660 KB Output isn't correct
73 Incorrect 881 ms 47032 KB Output isn't correct
74 Incorrect 899 ms 47036 KB Output isn't correct
75 Incorrect 917 ms 47036 KB Output isn't correct
76 Incorrect 887 ms 47032 KB Output isn't correct
77 Incorrect 911 ms 47028 KB Output isn't correct
78 Incorrect 948 ms 47036 KB Output isn't correct
79 Incorrect 943 ms 47044 KB Output isn't correct
80 Incorrect 936 ms 47040 KB Output isn't correct
81 Incorrect 949 ms 47092 KB Output isn't correct
82 Incorrect 908 ms 47040 KB Output isn't correct
83 Execution timed out 1086 ms 46944 KB Time limit exceeded
84 Execution timed out 1094 ms 46896 KB Time limit exceeded
85 Execution timed out 1039 ms 46916 KB Time limit exceeded
86 Execution timed out 1100 ms 46916 KB Time limit exceeded
87 Execution timed out 1082 ms 46916 KB Time limit exceeded
88 Execution timed out 1081 ms 47048 KB Time limit exceeded
89 Execution timed out 1092 ms 46916 KB Time limit exceeded
90 Execution timed out 1094 ms 47020 KB Time limit exceeded
91 Execution timed out 1092 ms 47016 KB Time limit exceeded
92 Execution timed out 1091 ms 46984 KB Time limit exceeded