Submission #1065625

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065625		belgianbot	Mecho (IOI09_mecho)	C++17	30 / 100	1072 ms	65536 KiB

mecho

#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;
	for (int x : hives) {
		priority_queue<pair<int,int>> q;
		q.push({0,x});
		set<int> processed;
		dist[x] = 0;
		
		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 (!dist.count(y)  || -u.fi + 1 < dist[y]) {
					dist[y] = -u.fi + 1;
					q.push({-dist[y], y});
				}
			}
		}
	}
	
	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 (stderr)

mecho.cpp: In function 'int main()':
mecho.cpp:78:23: warning: 'end' may be used uninitialized in this function [-Wmaybe-uninitialized]
   78 |   for (int y : adj[end]) if (mecho.count(y)) won = true;
      |                       ^

• Subtask 1: 30 / 100