Submission #1065682

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065682		belgianbot	Mecho (IOI09_mecho)	C++17	11 / 100	424 ms	65536 KiB

mecho

#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') 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);
	}
	
	vector<int> c(N * N, 0);
	priority_queue<vector<int>> q;
	set<int> st;
	q.push({-INT_MAX, start, 0});
	while (!q.empty()) {
		auto u = q.top(); q.pop();
		if (st.count(u[1])) continue;
		st.insert(u[1]);
		for (int y : adj[u[1]]) {
			if (min(-u[0], dist[y] - u[2] / S - 1) > c[y]) {
				c[y] = min(-u[0], dist[y] - u[2] / S - 1);
				q.push({-c[y], y, u[2] + 1});
			}
		}
	}
	int ans = 0;
	for (int x : adj[end]) ans = max(ans, c[x]);
	cout << ans << '\n';
	
	return 0;
}
		
	
	
	

Compilation message (stderr)

mecho.cpp: In function 'int main()':
mecho.cpp:66:22: warning: 'end' may be used uninitialized in this function [-Wmaybe-uninitialized]
   66 |  for (int x : adj[end]) ans = max(ans, c[x]);
      |                      ^
mecho.cpp:53:29: warning: 'start' may be used uninitialized in this function [-Wmaybe-uninitialized]
   53 |  q.push({-INT_MAX, start, 0});
      |                             ^

• Subtask 1: 11 / 100