Submission #607297

#	Time	Username	Problem	Language	Result	Execution time	Memory
607297		beaboss	Mecho (IOI09_mecho)	C++14	26 / 100	86 ms	21172 KiB

mecho

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main() {
	ll n, s;

	cin >> n>> s;

	vector<vector<char> > grid(n, vector<char>(n));
	queue<pair<ll ,ll> > q1;
	queue<pair<ll ,ll> > q2;
	pair<ll ,ll> home;
	pair<ll ,ll> start;


	vector<vector<ll> > hdist(n, vector<ll>(n, -1));
	vector<vector<ll> > mdist(n, vector<ll>(n, -1));

	for (ll i = 0; i < n; i++) for (ll j = 0; j < n; j++) {
		cin >> grid[i][j];
		if (grid[i][j] == 'H') {
			q1.push({i, j});
			hdist[i][j] = 0;
		}
		else if (grid[i][j] == 'M') {
			q2.push({i, j});
			mdist[i][j] = 0;
			start = {i, j};

		}
		else if (grid[i][j] == 'D') home = {i, j};
	}

	
	vector<ll> dx = {1, -1, 0, 0};
	vector<ll> dy = {0, 0, -1, 1};
	while (!q1.empty() && hdist[home.first][home.second] == -1) {
		pair<ll, ll> curr = q1.front();
		q1.pop();

		for (ll i = 0; i < 4; i++) {
			ll x = curr.first + dx[i];
			ll y = curr.second + dy[i];
			if (x >= 0 && x < n && y >= 0 && y < n) {
				if (hdist[x][y] == -1 && grid[x][y] == 'G') {
					hdist[x][y] = hdist[curr.first][curr.second] + s;
					q1.push({x, y});
					
				}
			}
		}

	}

	vector<vector<pair<ll, ll> > > parent(n, vector<pair<ll, ll> >(n, {-1, -1}));

	while (!q2.empty() && mdist[home.first][home.second] == -1) {
		pair<ll, ll> curr = q2.front();
		q2.pop();

		for (ll i = 0; i < 4; i++) {
			ll x = curr.first + dx[i];
			ll y = curr.second + dy[i];
			if (x >= 0 && x < n && y >= 0 && y < n) {
				if (mdist[x][y] == -1 && (grid[x][y] == 'G' || grid[x][y] == 'D') && (hdist[x][y] > mdist[curr.first][curr.second] + 1 || hdist[x][y ] == -1)) {
					mdist[x][y] = mdist[curr.first][curr.second] + 1;
					q2.push({x, y});
					
					parent[x][y] = {curr.first, curr.second};
				}
			}
		}

	}
	ll ans = 100000000;
	pair<ll ,ll> current = home;
	// cout << mdist[home.first][home.second] << endl;
	if (mdist[home.first][home.second] == -1) {
		cout << -1 << endl;
		return 0;
	}

	while (current != start) {
		ll x = current.first;
		ll y = current.second;
		if (hdist[x][y] != -1) {
			// cout << x << y << hdist[x][y] << endl;
			ans = min(ans, hdist[x][y]-mdist[x][y]);
		}
		current = parent[x][y];
	}
	// for (ll i = 0; i < 4; i++) {
	// 	ll x = home.first + dx[i];
	// 	ll y = home.second + dy[i];
	// 	if (x >= 0 && x < n && y >= 0 && y < n && grid[x][y] != 'T') {
	// 		ans = max(hdist[x][y] - mdist[x][y], ans);
	// 		cout << mdist[x][y] << hdist[x][y] << x << y << endl;
	// 	}
	// }
	cout << ans/s << endl;


	
	
}

• Subtask 1: 26 / 100