Submission #418029

#	Time	Username	Problem	Language	Result	Execution time	Memory
418029		gromperen	Mecho (IOI09_mecho)	C++17	12 / 100	377 ms	15804 KiB

mecho

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

#define ll long long

const int INF = 1e9+69;
const int MAXN = 805;

const int dx[4] = {0, 0, -1, 1};
const int dy[4] = {-1, 1, 0, 0};

vector<string> G(MAXN);
vector<vector<int>> G2(MAXN, vector<int>(MAXN,-1));
vector<vector<int>> G3(MAXN, vector<int>(MAXN,-1));

int n;
int s;

int sx, sy, ex, ey;

bool possible(int wait) {
	queue <tuple<int,int,int>> q;


	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			G3[i][j] = -1;
		}
	}
	if (wait * s >= G2[sx][sy]) {
		//cout << "BRUH" << endl;
		return false;
	}
	q.push({wait*s, sx, sy});
	while (!q.empty()) {
		int w = get<0>(q.front());
		int x = get<1>(q.front());
		int y = get<2>(q.front());
		//if (G[x][y] == 'D') {
			//cout << "YEH"<< endl;
		//}
		q.pop();
		if (G3[x][y] != -1) continue;
		G3[x][y] = w;
		for (int i = 0; i < 4 ;++i) {
			if (x + dx[i] < 0
					|| x + dx[i] >= n
					|| y + dy[i] < 0
					|| y + dy[i] >= n
					|| (G[x+dx[i]][y+dy[i]] == 'T')
					|| w+1 >= G2[x+dx[i]][y+dy[i]] ) {
				if (G[x+dx[i]][y+dy[i]] == 'D')
					q.push({w+1, x+dx[i], y+dy[i]});
				continue;
			}
			q.push({w+1, x+dx[i], y+dy[i]});
		}
	}
	//cout << endl;
	//cout << wait << endl;
	//for (int i = 0; i < n; ++i) {
		//for (int j = 0; j < n; ++j) {
			//cout << G3[i][j] << " ";
		//}
		//cout << endl;
	//}


	return G3[ex][ey] != -1;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);

	 cin >> n;
	 cin >> s;
	for (int i = 0; i < n; ++i) {
		cin >> G[i];
	}
	queue<tuple<int,int,int>> q;
	for (int i = 0; i < n; ++i) {
		for (int j  =0; j < n; ++j) {
			if (G[i][j] == 'H') {
				//G2[i][j] = 0;
				G2[i][j] = -1;
				q.push({0, i,j});
			} else {
				G2[i][j] = -1;
			}
			if (G[i][j] == 'M') {
				sx = i;
				sy = j;
			}
			if (G[i][j] == 'D') {
				ex = i;
				ey = j;
			}
		}
	}
	while(!q.empty()) {
		int w = get<0>(q.front());
		int x = get<1>(q.front());
		int y = get<2>(q.front());
		q.pop();
		if (G2[x][y] != -1) continue;
		G2[x][y] = w;
		for (int i = 0; i < 4; ++i) {
			if (x + dx[i] < 0
					|| x + dx[i] >= n
					|| y + dy[i] < 0
					|| y + dy[i] >= n
					|| (G[x+dx[i]][y+dy[i]] != 'G' && G[x+dx[i]][y+dy[i]] != 'M')) {
				continue;
			}
			q.push({w+s, x+dx[i], y+dy[i]});
		}
	}

	//for (int i = 0; i < n; ++i) {
		//for (int j  =0; j < n; ++j) {
			//cout << G2[i][j] << " ";
		//}
		//cout << endl;
	//}


	if (!possible(0)) {
		cout << "-1\n";
		return 0;
	}

	int l = 0, h = 800 * 800, m;
	while(l < h) {
		m = (l + h) / 2 + 1;
		if (possible(m)) {
			l = m;
		} else {
			h = m - 1;
		}
	}
	cout << l << "\n";

	return 0;
}

• Subtask 1: 12 / 100