Submission #104009

#	Time	Username	Problem	Language	Result	Execution time	Memory
104009		Erkhemkhuu	Mecho (IOI09_mecho)	C++17	11 / 100	1078 ms	66560 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define F first
#define S second
int movex[4] = {-1, 0, 1, 0};
int movey[4] = {0, 1, 0, -1};
char maps[805][805];
int beeStep[805][805], meStep[805][805], n, Mx, My, s, Dx, Dy;
queue <pair <int, int> > bee, me;
bool check(int x, int y) {
	if(x >= 0 && x < n && y >= 0 && y < n) return true;
	return false;
}
bool can(int mid) {
	memset(meStep, -1, sizeof(meStep));
	me.push(mp(Mx * 1000 + My, mid));
	while(!me.empty()) {
		int curx = me.front().F / 1000;
		int cury = me.front().F % 1000;
		int curstep = me.front().S;
		me.pop();
		if(meStep[curx][cury] != -1) continue;
		meStep[curx][cury] = curstep;
		for(int i = 0; i < 4; i++) {
			for(int i1 = 1; i1 <= s; i1++) {
				int movexx = movex[i] * i1 + curx;
				int moveyy = movey[i] * i1 + cury;
				if(check(movexx, moveyy) && maps[movexx][moveyy] != 'T' && meStep[movexx][moveyy] == -1) {
					if(beeStep[movexx][moveyy] != -1 && beeStep[movexx][moveyy] <= curstep) break;
					me.push(mp(movexx * 1000 + moveyy, curstep + 1));
				}
				else break;
			}
		}
	}
	//cout << meStep[Dx][Dy] << " " << beeStep[Dx][Dy] << "\n";
	if(beeStep[Dx][Dy] == -1) beeStep[Dx][Dy] = 1e9;
	if(meStep[Dx][Dy] == -1) return false;
	return meStep[Dx][Dy] <= beeStep[Dx][Dy];
}
int main() { 
	int i, j, l, r;
	scanf("%d%d", &n, &s);
	for(i = 0; i < n; i++) {
		scanf("%s", maps[i]);
		for(j = 0; j < n; j++) {
			if(maps[i][j] == 'H')
				bee.push(mp(i * 1000 + j, 0));
			if(maps[i][j] == 'M') {
				Mx = i; My = j;
			}
			if(maps[i][j] == 'D') {
				Dx = i; Dy = j;
			}
		}
	}
	memset(beeStep, -1, sizeof(beeStep));
	while(!bee.empty()) {
		int curx = bee.front().F / 1000;
		int cury = bee.front().F % 1000;
		int curstep = bee.front().S;
		bee.pop();
		if(beeStep[curx][cury] != -1) continue;
		beeStep[curx][cury] = curstep;
		for(int i = 0; i < 4; i++) {
			int movexx = movex[i] + curx;
			int moveyy = movey[i] + cury;
			if(check(movexx, moveyy) && maps[movexx][moveyy] != 'T' && beeStep[movexx][moveyy] == -1)
				bee.push(mp(movexx * 1000 + moveyy, curstep + 1));
		}
	}
	l = 0; r = 1e9;
	while(l != r) {
		int mid = (l + r + 1) / 2;
		if(can(mid)) l = mid ;
		else r = mid - 1;
	}
	printf("%d\n", l);
	return 0;
}

Compilation message (stderr)

mecho.cpp: In function 'int main()':
mecho.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &s);
  ~~~~~^~~~~~~~~~~~~~~~
mecho.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", maps[i]);
   ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 11 / 100