Submission #576693

#	Time	Username	Problem	Language	Result	Execution time	Memory
576693		Halym2007	Mecho (IOI09_mecho)	C++11	100 / 100	227 ms	11980 KiB

mecho

#include <bits/stdc++.h>
#define ff first
#define ss second
#define cont continue;
#define sz size()
#define pb push
using namespace std;
typedef long long ll;
const int N = 950;
int tr[4] = {1, -1, 0, 0};
int rt[4] = {0, 0, 1, -1};
void solve();
char a[N][N];
int dis[N][N], dis2[N][N];
int vis[N][N];
int a1,a2, a3, a4, jogap = -1, n, s;
queue < pair<int,int> > q;

bool barla (int x) {
	memset (vis, 0, sizeof (vis));
	memset (dis2, 0, sizeof (dis2));
	while (!q.empty()) q.pop();
	q.push({a1, a2});
	vis[a1][a2] = 1;
	if (x >= dis[a1][a2]) return 0;
	dis2[a1][a2] = 0;
	while (!q.empty()) {
		int b1 = q.front().ff;
		int b2 = q.front().ss;
		q.pop();
		for (int i = 0; i < 4; ++i) {
			int c1 = b1 + tr[i];
			int c2 = b2 + rt[i];
			if (c1 < 0 or c2 < 0 or c1 >= n or c2 >= n or a[c1][c2] == 'T' or a[c1][c2] == 'H') continue;
			if (vis[c1][c2]) continue;
			int kl = ceil((dis2[b1][b2] + 1) / (double) s) + x;
			int jp = ceil (dis2[b1][b2] / (double) s) + x;
			if (dis[b1][b2] == jp) {
				if (kl != jp) continue;
			}
			if (kl <= dis[c1][c2]) {
				dis2[c1][c2] = dis2[b1][b2] + 1;
				q.push({c1,c2});
				vis[c1][c2] = 1;
				if (a[c1][c2] == 'D') return 1;			
			}
		}
	}
	return 0;
}



int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	// freopen("input.txt", "r", stdin);
	// freopen("output.txt", "w", stdout);
	cin >> n >> s;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			dis[i][j] = 1e9;
			cin >> a[i][j];
			if (a[i][j] == 'M') {
				a1 = i;
				a[i][j] = 'G';
				a2 = j;
			}
			else if (a[i][j] == 'D') {
				a3 = i;
				a4 = j;
			}
		}
	}
	
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			if (a[i][j] == 'H') {
				q.push ({i, j});
				dis[i][j] = 0;
				vis[i][j] = 1;
			}
		}
	}
	while (!q.empty()) {
		int b1 = q.front().ff;
		int b2 = q.front().ss;
		q.pop();
		for (int i = 0; i < 4; ++i) {
			int c1 = b1 + tr[i];
			int c2 = b2 + rt[i];
			if (c1 < 0 or c2 < 0 or c1 >= n or c2 >= n or a[c1][c2] == 'T' or a[c1][c2] == 'D' or a[c1][c2] == 'H') continue;
			if (vis[c1][c2]) continue;	
			dis[c1][c2] = dis[b1][b2] + 1;
			vis[c1][c2] = 1;
			q.push({c1, c2});
		}
	}
	int l = 0, r = 850 * 850;
	while (l <= r) {
		int md = (l + r) / 2;
		if (barla(md)) {
			l = md + 1;
			jogap = md;	
		} 
		else r = md - 1;
	}
	cout << jogap;
	return 0;
} 

• Subtask 1: 100 / 100