Submission #954231

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
954231	2024-03-27T13:13:29 Z	tmtxangel	Mecho (IOI09_mecho)	C++17	16 / 100	1 ms	604 KB

mecho

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

const int MAX_N = 800;
vector<string> field(MAX_N);
int n, s;

bool valid_sq(int x, int y) {
	return x >= 0 && x < n && y >= 0 && y < n &&
	       (field[x][y] == 'G' || field[x][y] == 'M');
}

bool mecho_reached(int mecho_dis, int bees_dis) {
	return mecho_dis / s < bees_dis;
}

int main() {
	cin >> n >> s;
	for (int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++) cin >> field[i][j];
    }

	vector<pair<int, int>> hives;
	int mechox, mechoy, home_x, home_y;
	// find x and y coordinates for for Mecho, the bees and the cave
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (field[i][j] == 'M') {
				mechox = i;
				mechoy = j;
			} else if (field[i][j] == 'H') {
				hives.push_back({i, j});
			} else if (field[i][j] == 'D') {
				home_x = i;
				home_y = j;
			}
		}
	}

	int dx[] = {-1, 0, 1, 0};
	int dy[] = {0, -1, 0, 1};

	// binary search on waiting time
	int l = 0;
	int r = n * n;
	while (l <= r) {
		vector<vector<bool>> bees_visited(n, vector<bool>(n));
		vector<vector<bool>> mecho_visited(n, vector<bool>(n));
		vector<vector<int>> bees_time(n, vector<int>(n));
		vector<vector<int>> mecho_time(n, vector<int>(n));
		queue<pair<int, int>> q;

		int eating_time = (l + r) / 2;

		// move bees
		for (auto i : hives) {
			q.push({i.first, i.second});
			bees_visited[i.first][i.second] = true;
		}

		while (!q.empty()) {
			int x = q.front().first, y = q.front().second;
			q.pop();
			for (int i = 0; i < 4; i++) {
				int nx = x + dx[i], ny = y + dy[i];
				if (valid_sq(nx, ny) && !bees_visited[nx][ny]) {
					bees_time[nx][ny] = bees_time[x][y] + 1;
					q.push({nx, ny});
					bees_visited[nx][ny] = true;
				}
			}
		}

		// move Mecho
		q.push({mechox, mechoy});
		mecho_visited[mechox][mechoy] = true;
		if (bees_time[mechox][mechoy] <= eating_time) { q.pop(); }

		while (!q.empty()) {
			int x = q.front().first, y = q.front().second;
			q.pop();
			for (int i = 0; i < 4; i++) {
				int nx = x + dx[i], ny = y + dy[i];
				/*
				 * check if mecho reaces node[x][y] before the bees
				 * divide the time mecho takes to reach a node by s, since
				 * mecho walks s steps at a time.
				 * substract the eating time from the time taken for the
				 * bees to reach the node, because that time was used by
				 * mecho for eating
				 */
				if (valid_sq(nx, ny) && !mecho_visited[nx][ny] &&
				    mecho_reached(mecho_time[x][y] + 1,
				                  bees_time[nx][ny] - eating_time)) {
					mecho_visited[nx][ny] = true;
					q.push({nx, ny});
					mecho_time[nx][ny] = mecho_time[x][y] + 1;
				}
			}
		}

		// check if mecho reached a node surrounding his cave before the bees
		bool reached = false;
		for (int i = 0; i < 4; i++) {
			int nx = home_x + dx[i], ny = home_y + dy[i];
			if (valid_sq(nx, ny) &&
			    mecho_reached(mecho_time[nx][ny],
			                  bees_time[nx][ny] - eating_time) &&
			    mecho_visited[nx][ny]) {
				reached = true;
			}
		}
		if (reached) {
			l = eating_time + 1;
		} else {
			r = eating_time - 1;
		}
	}

	cout << l - 1 << '\n';
}

Compilation message

mecho.cpp: In function 'int main()':
mecho.cpp:77:23: warning: 'mechox' may be used uninitialized in this function [-Wmaybe-uninitialized]
   77 |   mecho_visited[mechox][mechoy] = true;
      |                       ^
mecho.cpp:106:29: warning: 'home_y' may be used uninitialized in this function [-Wmaybe-uninitialized]
  106 |    int nx = home_x + dx[i], ny = home_y + dy[i];
      |                             ^~
mecho.cpp:106:8: warning: 'home_x' may be used uninitialized in this function [-Wmaybe-uninitialized]
  106 |    int nx = home_x + dx[i], ny = home_y + dy[i];
      |        ^~

Subtask #1

16.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Runtime error	1 ms	600 KB	Execution killed with signal 11
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 ms	408 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Runtime error	1 ms	348 KB	Execution killed with signal 11
13	Runtime error	1 ms	348 KB	Execution killed with signal 11
14	Runtime error	1 ms	348 KB	Execution killed with signal 11
15	Runtime error	1 ms	348 KB	Execution killed with signal 11
16	Runtime error	0 ms	604 KB	Execution killed with signal 11
17	Runtime error	1 ms	348 KB	Execution killed with signal 11
18	Runtime error	0 ms	348 KB	Execution killed with signal 11
19	Runtime error	1 ms	360 KB	Execution killed with signal 11
20	Runtime error	1 ms	344 KB	Execution killed with signal 11
21	Runtime error	1 ms	600 KB	Execution killed with signal 11
22	Runtime error	1 ms	348 KB	Execution killed with signal 11
23	Runtime error	0 ms	348 KB	Execution killed with signal 11
24	Runtime error	1 ms	548 KB	Execution killed with signal 11
25	Runtime error	1 ms	348 KB	Execution killed with signal 11
26	Runtime error	1 ms	348 KB	Execution killed with signal 11
27	Runtime error	1 ms	348 KB	Execution killed with signal 11
28	Runtime error	1 ms	344 KB	Execution killed with signal 11
29	Runtime error	1 ms	344 KB	Execution killed with signal 11
30	Runtime error	1 ms	604 KB	Execution killed with signal 11
31	Runtime error	1 ms	348 KB	Execution killed with signal 11
32	Runtime error	1 ms	348 KB	Execution killed with signal 11
33	Runtime error	1 ms	348 KB	Execution killed with signal 11
34	Runtime error	1 ms	600 KB	Execution killed with signal 11
35	Runtime error	1 ms	348 KB	Execution killed with signal 11
36	Runtime error	1 ms	600 KB	Execution killed with signal 11
37	Runtime error	1 ms	348 KB	Execution killed with signal 11
38	Runtime error	1 ms	348 KB	Execution killed with signal 11
39	Runtime error	1 ms	348 KB	Execution killed with signal 11
40	Runtime error	1 ms	348 KB	Execution killed with signal 11
41	Runtime error	1 ms	348 KB	Execution killed with signal 11
42	Runtime error	1 ms	348 KB	Execution killed with signal 11
43	Runtime error	1 ms	604 KB	Execution killed with signal 11
44	Runtime error	1 ms	348 KB	Execution killed with signal 11
45	Runtime error	1 ms	604 KB	Execution killed with signal 11
46	Runtime error	1 ms	348 KB	Execution killed with signal 11
47	Runtime error	0 ms	348 KB	Execution killed with signal 11
48	Runtime error	1 ms	604 KB	Execution killed with signal 11
49	Runtime error	1 ms	348 KB	Execution killed with signal 11
50	Runtime error	1 ms	460 KB	Execution killed with signal 11
51	Runtime error	1 ms	348 KB	Execution killed with signal 11
52	Runtime error	1 ms	348 KB	Execution killed with signal 11
53	Runtime error	1 ms	348 KB	Execution killed with signal 11
54	Runtime error	1 ms	348 KB	Execution killed with signal 11
55	Runtime error	1 ms	348 KB	Execution killed with signal 11
56	Runtime error	1 ms	348 KB	Execution killed with signal 11
57	Runtime error	1 ms	604 KB	Execution killed with signal 11
58	Runtime error	0 ms	604 KB	Execution killed with signal 11
59	Runtime error	1 ms	348 KB	Execution killed with signal 11
60	Runtime error	1 ms	348 KB	Execution killed with signal 11
61	Runtime error	1 ms	348 KB	Execution killed with signal 11
62	Runtime error	1 ms	348 KB	Execution killed with signal 11
63	Runtime error	1 ms	348 KB	Execution killed with signal 11
64	Runtime error	1 ms	604 KB	Execution killed with signal 11
65	Runtime error	1 ms	348 KB	Execution killed with signal 11
66	Runtime error	1 ms	348 KB	Execution killed with signal 11
67	Runtime error	1 ms	348 KB	Execution killed with signal 11
68	Runtime error	1 ms	604 KB	Execution killed with signal 11
69	Runtime error	1 ms	600 KB	Execution killed with signal 11
70	Runtime error	1 ms	600 KB	Execution killed with signal 11
71	Runtime error	1 ms	600 KB	Execution killed with signal 11
72	Runtime error	1 ms	348 KB	Execution killed with signal 11
73	Runtime error	0 ms	348 KB	Execution killed with signal 11
74	Runtime error	1 ms	348 KB	Execution killed with signal 11
75	Runtime error	1 ms	600 KB	Execution killed with signal 11
76	Runtime error	1 ms	348 KB	Execution killed with signal 11
77	Runtime error	1 ms	600 KB	Execution killed with signal 11
78	Runtime error	1 ms	600 KB	Execution killed with signal 11
79	Runtime error	1 ms	604 KB	Execution killed with signal 11
80	Runtime error	0 ms	604 KB	Execution killed with signal 11
81	Runtime error	1 ms	348 KB	Execution killed with signal 11
82	Runtime error	1 ms	604 KB	Execution killed with signal 11
83	Runtime error	1 ms	348 KB	Execution killed with signal 11
84	Runtime error	1 ms	348 KB	Execution killed with signal 11
85	Runtime error	1 ms	600 KB	Execution killed with signal 11
86	Runtime error	1 ms	348 KB	Execution killed with signal 11
87	Runtime error	1 ms	348 KB	Execution killed with signal 11
88	Runtime error	1 ms	348 KB	Execution killed with signal 11
89	Runtime error	1 ms	348 KB	Execution killed with signal 11
90	Runtime error	1 ms	348 KB	Execution killed with signal 11
91	Runtime error	1 ms	348 KB	Execution killed with signal 11
92	Runtime error	1 ms	348 KB	Execution killed with signal 11