Submission #1103067

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103067		ef10	Mecho (IOI09_mecho)	C++17	32 / 100	1093 ms	65536 KiB

mecho

// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;

int N,S;
string M[1001];
struct node {
	int hd;
	int md;
	int hop;
};
bool v[1001][1001];
node all[1001][1001];
pair<int,int> m;

bool work(int e) {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			all[i][j].md = -1;
		}
	}

	queue<pair<int,int> > q;
	q.push(m);
	all[m.first][m.second].md = e;
	all[m.first][m.second].hop = 0;
	if (all[m.first][m.second].hd != -1 && all[m.first][m.second].hd <= e) return false;
	while (!q.empty()) {
		auto c = q.front();
						//cout << "handling " << c.first << "/" << c.second << "/" << all[c.first][c.second].md << endl;
		int cost = all[c.first][c.second].md+1;
		q.pop();
		queue<tuple<int,int,int> > tq;
		tq.push(make_tuple(c.first,c.second,0));
		while (!tq.empty()) {
			auto tc = tq.front();
			//cout << "    tq " << get<0>(tc) << "/" << get<1>(tc) << "/" << get<2>(tc) << endl;
			tq.pop();
			int hop = get<2>(tc)+1;
			if (hop > S) continue;
			for (auto i : {-1,1}) {
				for (int j = 0; j <= 1; j++) {
					int ti = j ? get<0>(tc) : (get<0>(tc)+i);
					int tj = j ? (get<1>(tc)+i) : (get<1>(tc));
					if (ti < 0 || ti >= N || tj < 0 || tj >= N) continue;
					//cout << "          " << ti << "/" << tj << " " << endl;
					if (M[ti][tj] == 'T') continue;
					if (all[ti][tj].md >= 0 && all[ti][tj].md < cost) continue;
					if (all[ti][tj].hd >= 0 && all[ti][tj].hd < cost) continue;
					if (M[ti][tj] == 'D') return true;
					if  (all[ti][tj].md == cost && all[ti][tj].hop <= hop) continue;
					if (hop == S && all[ti][tj].hd >= 0 && all[ti][tj].hd == cost) continue;
					//cout << "          " << ti << "/" << tj << "/" << hop << " passed" << endl;
					all[ti][tj].md = cost;
					all[ti][tj].hop = hop;
					if (all[ti][tj].hd > cost) {
						q.push(make_pair(ti,tj));
						//cout << "       add q " << ti << "/" << tj << "/" << cost << endl;
					}
					if (hop == S) continue;
					tq.push(make_tuple(ti,tj,hop));
				}
			}
		}
		/*for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				cout << all[i][j].md << "/" << all[i][j].hop << " ";
			}
			cout << endl;
		}*/
	}
	return false;
}

int solve() {
	int lo = 0, hi = 2*N;
		// if none of the values in the range work, return lo - 1
	lo--;
	while (lo < hi) {
		// find the middle of the current range (rounding up)
		int mid = lo + (hi - lo + 1) / 2;
		//cout << "mid: " << mid << ", " << lo << "/" << hi;
		if (work(mid)) {
			//cout << " worked" << endl;
			// if mid works, then all numbers smaller than mid also work
			lo = mid;
		} else {
			//cout << " not work" << endl;
			// if mid does not work, greater values would not work either
			hi = mid - 1;
		}
	}
	return lo;
}

int main() {
	cin >> N >> S;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			all[i][j].hd = -1;
		}
	}
	queue<pair<int,int> > q;
	for (int i = 0; i < N; i++) {
		cin >> M[i];
		for (int j = 0; j < N; j++) {
			if (M[i][j] == 'H') {
				all[i][j].hd = 0;
				q.push(make_pair(i,j));
			} else if (M[i][j] == 'M') {
				m = make_pair(i,j);
			}
		}
	}
	while (!q.empty()) {
		auto c = q.front();
		int cost = all[c.first][c.second].hd+1;
		q.pop();
		for (auto i : {-1,1}) {
			for (int j = 0; j <= 1; j++) {
				int ti = j ? c.first : c.first+i;
				int tj = j ? c.second+i : c.second;
				if (ti < 0 || ti >= N || tj < 0 || tj >= N) continue;
				if (M[ti][tj]=='T' || (all[ti][tj].hd!=-1 && all[ti][tj].hd<=cost)) continue;
				all[ti][tj].hd = cost;
				q.push(make_pair(ti,tj));
				//cout << "add " << ti << "/" << tj << endl;
			}
		}
	}
	/*for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cout << all[i][j].hd << " ";
		}
		cout << endl;
	}*/
	int r = solve();
	cout << r << endl;
	//cout << work(2) << endl;
}

• Subtask 1: 32 / 100