Submission #92081

#	Time	Username	Problem	Language	Result	Execution time	Memory
92081		arman_ferdous	Mecho (IOI09_mecho)	C++17	100 / 100	315 ms	7812 KiB

mecho

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

const int N = 800;
const int INF = 1e9+69;

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

int n, S;
string mat[N];

int beeDist[N][N], d[N][N];
bool vis[N][N];
int Mx, My, Dx, Dy;
queue< pair<int,int> > Q;

bool call(int T) {
	if(T * S >= beeDist[Mx][My]) return false;
	for(int i = 0; i < n; i++) 
		for(int j = 0; j < n; j++)
			vis[i][j] = false;

	vis[Mx][My] = true; d[Mx][My] = T * S;
	Q.push(make_pair(Mx,My));
	while(!Q.empty()) {
		auto it = Q.front(); Q.pop();
		int ux = it.first, uy = it.second;
		for(int k = 0; k < 4; k++) {
			int tx = ux + dx[k], ty = uy + dy[k];
			if(min(tx,ty) < 0 || max(tx,ty) >= n || mat[tx][ty] == 'T' || mat[tx][ty] == 'H' || vis[tx][ty] || d[ux][uy] + 1 >= beeDist[tx][ty]) continue;
			vis[tx][ty] = 1; d[tx][ty] = d[ux][uy] + 1; Q.push(make_pair(tx,ty));
		}
	} return vis[Dx][Dy];
}

int main() {
	cin >> n >> S;
	for(int i = 0; i < n; i++) cin >> mat[i];
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			beeDist[i][j] = INF;
			if(mat[i][j] == 'M') Mx = i, My = j;
			else if(mat[i][j] == 'D') Dx = i, Dy = j;
			else if(mat[i][j] == 'H') {
				Q.push(make_pair(i,j));
				beeDist[i][j] = 0;
			}
		}
	}
	while(!Q.empty()) {
		auto it = Q.front(); Q.pop();
		int ux = it.first, uy = it.second;
		for(int k = 0; k < 4; k++) {
			int tx = ux + dx[k];
			int ty = uy + dy[k];
			if(min(tx,ty) < 0 || max(tx,ty) >= n || mat[tx][ty] == 'T' || mat[tx][ty] == 'D' || beeDist[ux][uy] + S >= beeDist[tx][ty]) continue;
			beeDist[tx][ty] = beeDist[ux][uy] + S;
			Q.push(make_pair(tx,ty));
		}
	}
	int lo = 0, hi = n * n, ans = -1;
	while(lo <= hi) {
		int mid = (lo + hi) >> 1;
		if(call(mid)) ans = mid, lo = mid+1;
		else hi = mid-1;
	} cout << ans << "\n";
	return 0;
}

• Subtask 1: 100 / 100