제출 #1103071

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1103071		ef10	Mecho (IOI09_mecho)	C++17	53 / 100	119 ms	8440 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;
};
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 = 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();
			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;
					//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/S+e) continue;
					if (M[ti][tj] == 'D') return true;
					//cout << "          " << ti << "/" << tj << " passed" << endl;
					all[ti][tj].md = cost;
						q.push(make_pair(ti,tj));
						//cout << "       add q " << ti << "/" << tj << "/" << cost << endl;
				}
			}
		/*for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				cout << all[i][j].md << " ";
			}
			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 << endl;
		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' || M[ti][tj]=='D' || (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(3) << endl;
}

• Subtask 1: 53 / 100