Submission #433990

#	Time	Username	Problem	Language	Result	Execution time	Memory
433990		rainboy	Mecho (IOI09_mecho)	C11	100 / 100	229 ms	9024 KiB

mecho

#include <stdio.h>

#define N	800

int di[] = { -1, 1, 0, 0 };
int dj[] = { 0, 0, -1, 1 };

char cc[N][N + 1];

int dd_[N][N], dd[N][N], qu[N * N], n, s;

int solve(int im, int jm, int id, int jd, int t) {
	int i, j, head, cnt;

	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++)
			dd[i][j] = n * n;
	head = cnt = 0;
	dd[im][jm] = 0, qu[head + cnt++] = im * n + jm;
	while (cnt) {
		int ij, h, d;

		ij = qu[cnt--, head++], i = ij / n, j = ij % n, d = dd[i][j] + 1;
		if (dd_[i][j] <= t + dd[i][j] / s)
			continue;
		if (i == id && j == jd)
			return 1;
		for (h = 0; h < 4; h++) {
			int i_ = i + di[h], j_ = j + dj[h];

			if (i_ >= 0 && i_ < n && j_ >= 0 && j_ < n && cc[i_][j_] != 'T' && dd[i_][j_] > d)
				dd[i_][j_] = d, qu[head + cnt++] = i_ * n + j_;
		}
	}
	return 0;
}

int main() {
	int i, j, im, jm, id, jd, head, cnt, lower, upper;

	scanf("%d%d", &n, &s);
	for (i = 0; i < n; i++)
		scanf("%s", cc[i]);
	head = cnt = 0;
	im = jm = id = jd = -1;
	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++) {
			if (cc[i][j] == 'H')
				dd_[i][j] = 0, qu[head + cnt++] = i * n + j;
			else
				dd_[i][j] = n * n;
			if (cc[i][j] == 'M')
				im = i, jm = j;
			else if (cc[i][j] == 'D')
				id = i, jd = j;
		}
	while (cnt) {
		int ij, d, h;

		ij = qu[cnt--, head++], i = ij / n, j = ij % n, d = dd_[i][j] + 1;
		for (h = 0; h < 4; h++) {
			int i_ = i + di[h], j_ = j + dj[h];

			if (i_ >= 0 && i_ < n && j_ >= 0 && j_ < n && (cc[i_][j_] == 'G' || cc[i_][j_] == 'M') && dd_[i_][j_] > d)
				dd_[i_][j_] = d, qu[head + cnt++] = i_ * n + j_;
		}
	}
	lower = -1, upper = n * n + 1;
	while (upper - lower > 1) {
		int t = (lower + upper) / 2;

		if (solve(im, jm, id, jd, t))
			lower = t;
		else
			upper = t;
	}
	printf("%d\n", lower);
	return 0;
}

Compilation message (stderr)

mecho.c: In function 'main':
mecho.c:41:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |  scanf("%d%d", &n, &s);
      |  ^~~~~~~~~~~~~~~~~~~~~
mecho.c:43:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |   scanf("%s", cc[i]);
      |   ^~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100