Submission #838432

#	Time	Username	Problem	Language	Result	Execution time	Memory
838432		cryan	Mecho (IOI09_mecho)	C++17	9 / 100	928 ms	65536 KiB

mecho

// oh, these hills, they burn so bright / oh, these hills, they bring me life
#include "bits/stdc++.h"
using namespace std;

using ll = long long;
#define all(x) begin(x), end(x)
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)(x.size())
#define inf 1000000010
#define linf 0x3f3f3f3f3f3f3f3f
#define mp make_pair
#define f first
#define s second
#define pi pair<int, int>
#define endl '\n'
#ifdef LOCAL
#include "/mnt/c/yukon/pp.hpp"
#endif

vector<int> dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1};
int main() {
	cin.tie(0)->sync_with_stdio(0);

	int n, S;
	cin >> n >> S;

	vector<vector<int>> grid(n, vector<int>(n));
	pi st, ed;
	queue<array<int, 3>> q;
	vector<vector<int>> bist(n, vector<int>(n, 9));
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < n; j++) {
			if (s[j] == 'T') {
				grid[i][j] = -1;
			} else if (s[j] == 'G') {
				grid[i][j] = 0;
			} else if (s[j] == 'M') {
				grid[i][j] = 0;
				st = {i, j};
			} else if (s[j] == 'D') {
				grid[i][j] = 0;
				ed = {i, j};
			} else {
				grid[i][j] = 1;
				bist[i][j] = 0;
				q.push({i, j, 0});
			}
		}
	}

	// dist from hives first
	while (sz(q)) {
		auto [i, j, di] = q.front();
		q.pop();

		for (int d = 0; d < 4; d++) {
			int ni = i + dx[d], nj = j + dy[d];
			if (ni >= 0 && ni < n && nj >= 0 && nj < n && grid[ni][nj] != -1 && di + 1 < bist[ni][nj]) {
				bist[ni][nj] = di + 1;
				q.push({ni, nj, di + 1});
			}
		}
	}
	// for (int i = 0; i < n; i++) {
	// 	cerr << bist[i] << endl;
	// }

	vector<vector<pi>> fastest(n, vector<pi>(n, {-inf, 0}));
	fastest[st.f][st.s] = {bist[st.f][st.s], 1};

	q.push({st.f, st.s, 0});

	map<pi, pi> prev;
	while (sz(q)) {
		auto [i, j, d] = q.front();
		q.pop();
		// cout << "start from: " << i << ' ' << j << " with distance " << d << endl;

		for (int dir = 0; dir < 4; dir++) {
			int ni = i + dx[dir], nj = j + dy[dir];

			int mins = (d + 1) / S;

			if (ni >= 0 && ni < n && nj >= 0 && nj < n && grid[ni][nj] != -1) {
				if (mins <= bist[ni][nj]) {

					int best = min(fastest[i][j].f, bist[ni][nj] - mins);
					if (best == -inf) {
						// cout << "fastest[" << ni << "][" << nj << "] = {" << best << ", " << (bool)((d + 1) % S > 0) << "}" << endl;
						fastest[ni][nj] = {bist[ni][nj] - mins, (d + 1) % S > 0};
						prev[{ni, nj}] = {i, j};
						q.push({ni, nj, d + 1});
					} else if (best > fastest[ni][nj].f || (best == fastest[ni][nj].f && (d + 1) % S > fastest[ni][nj].s)) {
						// cout << "fastest[" << ni << "][" << nj << "] = {" << best << ", " << (bool)((d + 1) % S > 0) << "}" << endl;
						fastest[ni][nj] = {best, (d + 1) % S > 0};
						prev[{ni, nj}] = {i, j};
						q.push({ni, nj, d + 1});
					}
				}
			}
		}
	}
	// cout << "path:" << endl;
	// auto tmp = ed;
	// while (tmp != pi{0, 0}) {
	// 	cout << tmp << endl;
	// 	tmp = prev[tmp];
	// }

	cout << (fastest[ed.f][ed.s].f == -inf ? -1 : fastest[ed.f][ed.s].f - 1) << endl;
}

// don't get stuck on one approach
// question bounds
// flesh out your approach before implementing o.o
// math it out
// ok well X is always possible, how about X + 1 (etc.)

• Subtask 1: 9 / 100