oj.uz

Submission #1065968

# Submission time Handle Problem Language Result Execution time Memory
1065968 2024-08-19T13:40:48 Z belgianbot Mecho (IOI09_mecho) C++17
12 / 100
 407 ms 65536 KB 
#include <bits/stdc++.h>
#define se second
#define fi first

using namespace std;

signed main() {
	ios::sync_with_stdio(false);
	//cin.tie(0);
	int N, S; cin >> N >> S;
	vector<vector<char>> grid(N, vector<char>(N));
	
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) cin >> grid[i][j];
	}
	
	int start, end;
	vector<vector<int>> adj(N * N);
	vector<int> hives;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (grid[i][j] == 'H') hives.push_back(i * N + j);
			else if (grid[i][j] == 'M') start = i * N + j;
			else if (grid[i][j] == 'D') end = i * N + j;
			if (grid[i][j] != 'G' && grid[i][j] != 'D') continue;
			if (i && (grid[i - 1][j] == 'D' || grid[i - 1][j] == 'H' || grid[i - 1][j] == 'M' || grid[i - 1][j] == 'G')) adj[i * N - N + j].push_back(i * N + j);
			if (j && (grid[i][j-1] == 'D' || grid[i][j-1] == 'H' || grid[i][j-1] == 'M' || grid[i][j-1] == 'G')) adj[i * N + j-1].push_back(i * N + j);
			if (i != N - 1 && (grid[i + 1][j] == 'D' || grid[i + 1][j] == 'H' || grid[i + 1][j] == 'M' || grid[i + 1][j] == 'G')) adj[i * N + N + j].push_back(i * N + j);
			if (j != N - 1 && (grid[i][j+1] == 'D' || grid[i][j+1] == 'H' || grid[i][j+1] == 'M' || grid[i][j+1] == 'G')) adj[i * N + j+1].push_back(i * N + j);
		}
	}
	
	vector<int> dist(N * N, INT_MAX);
	set<int> processed;
	int cnt = 1;
	while (!hives.empty()) {
		vector<int> newHives;
		for (int x : hives) {
			for (int y : adj[x]) {
				if (processed.count(y)) continue;
				dist[y] = cnt;
				processed.insert(y); 
				newHives.push_back(y);
			}
		}
		cnt++;
		swap(hives, newHives);
	}
	
	int l = 1, r = N * N;
	while (l <= r) {
		int mid = l + (r - l) / 2;
		queue<pair<int,int>> q;
		q.push({mid * S, start});
		bool won = false;
		while (!q.empty()) {
			auto u = q.front(); q.pop();
			if (u.se == end) {
				won = true;
				break;
			}
			if (u.fi / S >= dist[u.se]) continue;
			for (int x : adj[u.se]) q.push({u.fi + 1, x});
		}

		if (won) l = mid + 1;
		else r = mid - 1;
	}
	
	cout << l - 1 << '\n';
	return 0;
}

Compilation message

mecho.cpp: In function 'int main()':
mecho.cpp:58:4: warning: 'end' may be used uninitialized in this function [-Wmaybe-uninitialized]
   58 |    if (u.se == end) {
      |    ^~

Subtask #1
12.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 3 ms 860 KB Output is correct
7 Runtime error 363 ms 65536 KB Execution killed with signal 9
8 Incorrect 1 ms 348 KB Output isn't correct
9 Correct 19 ms 10008 KB Output is correct
10 Correct 3 ms 860 KB Output is correct
11 Runtime error 120 ms 65536 KB Execution killed with signal 9
12 Incorrect 1 ms 604 KB Output isn't correct
13 Runtime error 122 ms 65536 KB Execution killed with signal 9
14 Runtime error 110 ms 65536 KB Execution killed with signal 9
15 Runtime error 368 ms 65536 KB Execution killed with signal 9
16 Runtime error 167 ms 65536 KB Execution killed with signal 9
17 Runtime error 146 ms 65536 KB Execution killed with signal 9
18 Runtime error 137 ms 65536 KB Execution killed with signal 9
19 Runtime error 163 ms 65536 KB Execution killed with signal 9
20 Runtime error 150 ms 65536 KB Execution killed with signal 9
21 Runtime error 145 ms 65536 KB Execution killed with signal 9
22 Runtime error 144 ms 65536 KB Execution killed with signal 9
23 Runtime error 157 ms 65536 KB Execution killed with signal 9
24 Runtime error 138 ms 65536 KB Execution killed with signal 9
25 Runtime error 161 ms 65536 KB Execution killed with signal 9
26 Runtime error 148 ms 65536 KB Execution killed with signal 9
27 Runtime error 145 ms 65536 KB Execution killed with signal 9
28 Runtime error 141 ms 65536 KB Execution killed with signal 9
29 Runtime error 353 ms 65536 KB Execution killed with signal 9
30 Runtime error 138 ms 65536 KB Execution killed with signal 9
31 Runtime error 147 ms 65536 KB Execution killed with signal 9
32 Runtime error 150 ms 65536 KB Execution killed with signal 9
33 Runtime error 148 ms 65536 KB Execution killed with signal 9
34 Runtime error 138 ms 65536 KB Execution killed with signal 9
35 Runtime error 157 ms 65536 KB Execution killed with signal 9
36 Runtime error 153 ms 65536 KB Execution killed with signal 9
37 Runtime error 145 ms 65536 KB Execution killed with signal 9
38 Runtime error 169 ms 65536 KB Execution killed with signal 9
39 Runtime error 149 ms 65536 KB Execution killed with signal 9
40 Runtime error 134 ms 65536 KB Execution killed with signal 9
41 Runtime error 192 ms 65536 KB Execution killed with signal 9
42 Runtime error 143 ms 65536 KB Execution killed with signal 9
43 Runtime error 145 ms 65536 KB Execution killed with signal 9
44 Runtime error 211 ms 65536 KB Execution killed with signal 9
45 Runtime error 159 ms 65536 KB Execution killed with signal 9
46 Runtime error 164 ms 65536 KB Execution killed with signal 9
47 Runtime error 216 ms 65536 KB Execution killed with signal 9
48 Runtime error 164 ms 65536 KB Execution killed with signal 9
49 Runtime error 152 ms 65536 KB Execution killed with signal 9
50 Runtime error 273 ms 65536 KB Execution killed with signal 9
51 Runtime error 167 ms 65536 KB Execution killed with signal 9
52 Runtime error 168 ms 65536 KB Execution killed with signal 9
53 Runtime error 279 ms 65536 KB Execution killed with signal 9
54 Runtime error 159 ms 65536 KB Execution killed with signal 9
55 Runtime error 158 ms 65536 KB Execution killed with signal 9
56 Runtime error 284 ms 65536 KB Execution killed with signal 9
57 Runtime error 151 ms 65536 KB Execution killed with signal 9
58 Runtime error 152 ms 65536 KB Execution killed with signal 9
59 Runtime error 315 ms 65536 KB Execution killed with signal 9
60 Runtime error 146 ms 65536 KB Execution killed with signal 9
61 Runtime error 158 ms 65536 KB Execution killed with signal 9
62 Runtime error 351 ms 65536 KB Execution killed with signal 9
63 Runtime error 278 ms 65536 KB Execution killed with signal 9
64 Runtime error 285 ms 65536 KB Execution killed with signal 9
65 Runtime error 270 ms 65536 KB Execution killed with signal 9
66 Runtime error 258 ms 65536 KB Execution killed with signal 9
67 Runtime error 238 ms 65536 KB Execution killed with signal 9
68 Runtime error 284 ms 65536 KB Execution killed with signal 9
69 Runtime error 259 ms 65536 KB Execution killed with signal 9
70 Runtime error 265 ms 65536 KB Execution killed with signal 9
71 Runtime error 265 ms 65536 KB Execution killed with signal 9
72 Runtime error 255 ms 65536 KB Execution killed with signal 9
73 Runtime error 407 ms 65536 KB Execution killed with signal 9
74 Runtime error 407 ms 65536 KB Execution killed with signal 9
75 Runtime error 388 ms 65536 KB Execution killed with signal 9
76 Runtime error 369 ms 65536 KB Execution killed with signal 9
77 Runtime error 379 ms 65536 KB Execution killed with signal 9
78 Runtime error 339 ms 65536 KB Execution killed with signal 9
79 Runtime error 335 ms 65536 KB Execution killed with signal 9
80 Runtime error 333 ms 65536 KB Execution killed with signal 9
81 Runtime error 348 ms 65536 KB Execution killed with signal 9
82 Runtime error 368 ms 65536 KB Execution killed with signal 9
83 Runtime error 340 ms 65536 KB Execution killed with signal 9
84 Runtime error 388 ms 65536 KB Execution killed with signal 9
85 Runtime error 361 ms 65536 KB Execution killed with signal 9
86 Runtime error 352 ms 65536 KB Execution killed with signal 9
87 Runtime error 372 ms 65536 KB Execution killed with signal 9
88 Runtime error 370 ms 65536 KB Execution killed with signal 9
89 Runtime error 407 ms 65536 KB Execution killed with signal 9
90 Runtime error 372 ms 65536 KB Execution killed with signal 9
91 Runtime error 375 ms 65536 KB Execution killed with signal 9
92 Runtime error 404 ms 65536 KB Execution killed with signal 9