제출 #700213

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
700213		AverageAmogusEnjoyer	Mecho (IOI09_mecho)	C++17	22 / 100	1092 ms	7516 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define nl '\n'
using ll = long long;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int N, S; cin >> N >> S;
	vector<vector<char>> grid(N, vector<char> (N));
	pair<int, int> Mecho, House;
	vector<pair<int, int>> hives;
	for (int a=0; a<N; a++) {
		for (int b=0; b<N; b++) {
			cin >> grid[a][b];
			if (grid[a][b] == 'M') {
				grid[a][b] = 'T';
				Mecho = {a, b};
			}	
			if (grid[a][b] == 'D') {
				House = {a, b};
			}
			if (grid[a][b] == 'H') {
				hives.pb({a, b});
			}
		}
	}
	int a=0, b = 1e9;
	while(a <= b) {
		int h = (a+b)/2;
		vector<vector<int>> time(N, vector<int> (N));
		vector<vector<bool>> used(N, vector<bool> (N)), usedMecho(N, vector<bool> (N));
		deque<tuple<int, int, int>> q;
		for (auto n: hives) {
			q.pb({n.first, n.second, 0});
			used[n.first][n.second] = 1;
		}
		bool mechoIn = 0;
		while(!q.empty()) {
			int x, y, isMecho;
			tie(x, y, isMecho) = q.back();
			q.pop_back();
			vector<pair<int, int>> moves = {{x-1, y}, {x+1, y}, {x, y-1}, {x, y+1}};
			if (isMecho > S) {
				q.push_front({x, y, 1});
				usedMecho[x][y] = 1;
				continue;
			}
			for (auto move: moves) {
				if (move.first >= 0 && move.second >= 0 && move.first < N && move.second < N && grid[move.first][move.second] != 'T' && !used[move.first][move.second]) {
					if (isMecho > 0 && isMecho - 1 < S && !usedMecho[move.first][move.second]) {
						usedMecho[move.first][move.second] = 1;
						q.push_back({move.first, move.second, isMecho+1});
					} else if (grid[move.first][move.second] != 'D') {
						time[move.first][move.second] = time[x][y] + 1;
						if (!mechoIn && time[move.first][move.second] == h-1) {
							mechoIn = 1;
							q.push_front({Mecho.first, Mecho.second, 1});
							usedMecho[Mecho.first][Mecho.second] = 1;
						}
						used[move.first][move.second] = 1;
						q.push_front({move.first, move.second, 0});
					}
				}
			}
		}
		// if (h == 2) {
		// 	for (int e=0; e<N; e++) {
		// 		for (int f=0; f<N; f++) {
		// 			cout << usedMecho[e][f] << " ";
		// 		}
		// 		cout << nl;
		// 	}
		// 	cout << nl << nl;
		// 	for (int e=0; e<N; e++) {
		// 		for (int f=0; f<N; f++) {
		// 			cout << used[e][f] << " ";
		// 		}
		// 		cout << nl;
		// 	}
		// }
		// if (usedMecho[2][4]) {
		// 	cout << h << nl << nl;
		// 	for (int e=0; e<N; e++) {
		// 		for (int f=0; f<N; f++) {
		// 			cout << usedMecho[e][f] << " ";
		// 		}
		// 		cout << nl;
		// 	}
		// 	cout << nl << nl;
		// 	for (int e=0; e<N; e++) {
		// 		for (int f=0; f<N; f++) {
		// 			cout << used[e][f] << " ";
		// 		}
		// 		cout << nl;
		// 	}
		// }
		if (usedMecho[House.first][House.second]) {
			a = h + 1;
		} else b = h - 1;
	}
	cout << (b == -1 ? b: --b); 
}

• Subtask 1: 22 / 100