Submission #1066054

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066054		belgianbot	Mecho (IOI09_mecho)	C++17	42 / 100	244 ms	65540 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<string> grid(N);
	
	for (int i = 0; i < N; i++) {
		cin >> grid[i];
	}
	
	int start, end;
	vector<int> dist(N * N, INT_MAX);
	vector<vector<int>> adj(N * N);
	queue<pair<int,int>> hives;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (grid[i][j] == 'H') {
				hives.push({i * N + j, 1});
				dist[i * N + j] = 0;
			}
			else if (grid[i][j] == 'M') start = i * N + j;
			else if (grid[i][j] == 'D') end = i * N + j;
			if (grid[i][j] == 'H' || grid[i][j] == 'T') 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);
		}
	}
	
	
	while (!hives.empty()) {
		auto x = hives.front(); hives.pop();
		for (int y : adj[x.fi]) {
			if (dist[y] == INT_MAX && grid[y / N][y % N] != 'D'){
				hives.push({y, x.se + 1});
				dist[y] = x.se;
			}
		}
	}
	int maxi = 0;
	for (int x : adj[end]) maxi = max(maxi, dist[x] != INT_MAX ? dist[x] : 0);
	vector<bool> pro;
	int l = 0, r = N * N / 2 + N;
	while (l <= r) {
		int mid = l + (r - l) / 2;
		pro.clear(); pro.resize(N * N, false);
		queue<pair<int,int>> q;
		q.push({mid * S, start});
		bool won = false;
		while (!q.empty() && !won && q.front().fi / S < maxi) {
			auto u = q.front(); q.pop();
			pro[u.se] = true;
			for (int x : adj[u.se]) {
				if (x == end) {won = true; break;}
				if (!pro[x] && (u.fi + 1) / S < dist[x]) q.push({u.fi + 1, x});
			}
		}

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

Compilation message (stderr)

mecho.cpp: In function 'int main()':
mecho.cpp:48:22: warning: 'end' may be used uninitialized in this function [-Wmaybe-uninitialized]
   48 |  for (int x : adj[end]) maxi = max(maxi, dist[x] != INT_MAX ? dist[x] : 0);
      |                      ^

• Subtask 1: 42 / 100