oj.uz

Submission #1065634

# Submission time Handle Problem Language Result Execution time Memory
1065634 2024-08-19T10:14:56 Z belgianbot Mecho (IOI09_mecho) C++17
30 / 100
 1000 ms 65536 KB 
#include <bits/stdc++.h>
#define int long long
#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') 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);
		}
	}
	
	map<int,int> dist;
	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;
		
		map<int, double> mecho;
		mecho[start] = mid;
		priority_queue<pair<double,int>> q;
		q.push({double(-mid), start});
		set<int> processed;
		
		while(!q.empty()) {
			auto u = q.top(); q.pop();
			if (processed.find(u.se) != processed.end()) continue;
			processed.insert(u.se);
			
			for (int y : adj[u.se]) {
				if (-u.fi + 1.0 / double(S) < dist[y] && (!mecho.count(y) || -u.fi + 1.0 / double(S) < mecho[y]) ) {
					mecho[y] = -u.fi + 1.0 / double(S);
					q.push({-mecho[y], y});
				}
			}
		}
		bool won = false;
		for (int y : adj[end]) if (mecho.count(y)) won = true;
		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:74:23: warning: 'end' may be used uninitialized in this function [-Wmaybe-uninitialized]
   74 |   for (int y : adj[end]) if (mecho.count(y)) won = true;
      |                       ^

Subtask #1
30.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 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 1 ms 392 KB Output is correct
7 Runtime error 164 ms 65536 KB Execution killed with signal 9
8 Incorrect 0 ms 344 KB Output isn't correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Incorrect 1 ms 604 KB Output isn't correct
13 Incorrect 2 ms 860 KB Output isn't correct
14 Incorrect 7 ms 1116 KB Output isn't correct
15 Correct 0 ms 452 KB Output is correct
16 Correct 1 ms 424 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 604 KB Output is correct
22 Correct 1 ms 604 KB Output is correct
23 Correct 1 ms 600 KB Output is correct
24 Correct 1 ms 604 KB Output is correct
25 Correct 2 ms 856 KB Output is correct
26 Correct 2 ms 856 KB Output is correct
27 Correct 2 ms 860 KB Output is correct
28 Correct 2 ms 860 KB Output is correct
29 Correct 2 ms 860 KB Output is correct
30 Correct 2 ms 860 KB Output is correct
31 Correct 2 ms 860 KB Output is correct
32 Correct 3 ms 1368 KB Output is correct
33 Correct 43 ms 13908 KB Output is correct
34 Correct 59 ms 15444 KB Output is correct
35 Execution timed out 1044 ms 27116 KB Time limit exceeded
36 Correct 50 ms 18004 KB Output is correct
37 Correct 79 ms 20052 KB Output is correct
38 Execution timed out 1101 ms 35516 KB Time limit exceeded
39 Correct 69 ms 22704 KB Output is correct
40 Correct 95 ms 25172 KB Output is correct
41 Execution timed out 1054 ms 44700 KB Time limit exceeded
42 Correct 100 ms 27868 KB Output is correct
43 Correct 123 ms 31056 KB Output is correct
44 Execution timed out 1022 ms 54608 KB Time limit exceeded
45 Correct 104 ms 33568 KB Output is correct
46 Correct 157 ms 37588 KB Output is correct
47 Runtime error 971 ms 65536 KB Execution killed with signal 9
48 Correct 133 ms 40016 KB Output is correct
49 Correct 190 ms 44660 KB Output is correct
50 Runtime error 465 ms 65536 KB Execution killed with signal 9
51 Correct 149 ms 46672 KB Output is correct
52 Correct 212 ms 52304 KB Output is correct
53 Runtime error 354 ms 65536 KB Execution killed with signal 9
54 Correct 182 ms 54100 KB Output is correct
55 Correct 276 ms 60752 KB Output is correct
56 Runtime error 342 ms 65536 KB Execution killed with signal 9
57 Correct 224 ms 62032 KB Output is correct
58 Runtime error 177 ms 65536 KB Execution killed with signal 9
59 Runtime error 279 ms 65536 KB Execution killed with signal 9
60 Runtime error 137 ms 65536 KB Execution killed with signal 9
61 Runtime error 158 ms 65536 KB Execution killed with signal 9
62 Runtime error 239 ms 65536 KB Execution killed with signal 9
63 Runtime error 278 ms 65536 KB Execution killed with signal 9
64 Runtime error 273 ms 65536 KB Execution killed with signal 9
65 Runtime error 301 ms 65536 KB Execution killed with signal 9
66 Runtime error 342 ms 65536 KB Execution killed with signal 9
67 Runtime error 267 ms 65536 KB Execution killed with signal 9
68 Runtime error 282 ms 65536 KB Execution killed with signal 9
69 Runtime error 273 ms 65536 KB Execution killed with signal 9
70 Runtime error 279 ms 65536 KB Execution killed with signal 9
71 Runtime error 275 ms 65536 KB Execution killed with signal 9
72 Runtime error 273 ms 65536 KB Execution killed with signal 9
73 Runtime error 164 ms 65536 KB Execution killed with signal 9
74 Runtime error 164 ms 65536 KB Execution killed with signal 9
75 Runtime error 158 ms 65536 KB Execution killed with signal 9
76 Runtime error 159 ms 65536 KB Execution killed with signal 9
77 Runtime error 155 ms 65536 KB Execution killed with signal 9
78 Runtime error 165 ms 65536 KB Execution killed with signal 9
79 Runtime error 166 ms 65536 KB Execution killed with signal 9
80 Runtime error 158 ms 65536 KB Execution killed with signal 9
81 Runtime error 186 ms 65536 KB Execution killed with signal 9
82 Runtime error 162 ms 65536 KB Execution killed with signal 9
83 Runtime error 162 ms 65536 KB Execution killed with signal 9
84 Runtime error 199 ms 65536 KB Execution killed with signal 9
85 Runtime error 178 ms 65536 KB Execution killed with signal 9
86 Runtime error 205 ms 65536 KB Execution killed with signal 9
87 Runtime error 174 ms 65536 KB Execution killed with signal 9
88 Runtime error 172 ms 65536 KB Execution killed with signal 9
89 Runtime error 179 ms 65536 KB Execution killed with signal 9
90 Runtime error 190 ms 65536 KB Execution killed with signal 9
91 Runtime error 170 ms 65536 KB Execution killed with signal 9
92 Runtime error 166 ms 65536 KB Execution killed with signal 9