Submission #607338

#	Time	Username	Problem	Language	Result	Execution time	Memory
607338		beaboss	Mecho (IOI09_mecho)	C++14	73 / 100	435 ms	21428 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));

	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});
			
			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' || grid[x][y] == 'D')) {
					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}));
	ll hi = n*n;
	ll lo = 0;
	while (hi > lo || (hi == 0 && lo == 0)) {

		ll mid = (hi + lo + 1)/2;
		// cout << hi << lo << endl;
		vector<vector<ll> > mdist(n, vector<ll>(n, -1));
		mdist[start.first][start.second] = mid * s;
		q2.push(start);
		// cout << hdist[3][1] << endl;
		while (!q2.empty()) {
			pair<ll, ll> curr = q2.front();
			// cout << mdist[curr.first][curr.second] << endl;
			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};
					}
				}
			}

		}
		if (mdist[home.first][home.second] != -1) {
			lo = mid;
			if (hi == 0 && lo == 0) break;
		} else {
			hi = mid - 1;
		}
	}
	// 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 << hi << endl;


	
	
}

• Subtask 1: 73 / 100