Submission #1194099

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194099		anastasiskolio	Mecho (IOI09_mecho)	C++20	11 / 100	211 ms	6480 KiB

mecho

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <queue>
#include <array>
#define MAXN 800
#define INF 1000000
using namespace std;

queue<pair<int, int>> Qb;
queue<array<int, 3>> Qm;
vector<vector<char>> A(MAXN, vector<char>(MAXN));
vector<vector<int>> Db(MAXN, vector<int>(MAXN));
vector<vector<int>> Dm(MAXN, vector<int>(MAXN));
int N;
int S;
int Si;
int Sj;
int Ti;
int Tj;

void BeesGoTo(int i, int j, int D) {
	if (i >= 0 && i < N && j >= 0 && j < N && A[i][j] != 'T' && A[i][j] != 'D' && Db[i][j] == INF) {
		Db[i][j] = D + 1;
		Qb.push({ i, j });
	}
}

void BeesBreadthFirstSearch() {
	while (!Qb.empty()) {
		int i = Qb.front().first;
		int j = Qb.front().second;
		Qb.pop();
		BeesGoTo(i + 1, j, Db[i][j]);
		BeesGoTo(i - 1, j, Db[i][j]);
		BeesGoTo(i, j + 1, Db[i][j]);
		BeesGoTo(i, j - 1, Db[i][j]);
	}
}

void MechoGoTo(int i, int j, int s, int D) {
	if (i >= 0 && i < N && j >= 0 && j < N && A[i][j] != 'T' && A[i][j] != 'H' && Dm[i][j] == INF && D + !s < Db[i][j]) {
		Dm[i][j] = D + !s;
		Qm.push({ i, j, !s ? S : --s });
	}
}


bool MechoBreadthFirstSearch(int T) {
	for (int i = 0; i < N; ++i)
		for (int j = 0; j < N; ++j)
			Dm[i][j] = INF;
	Dm[Si][Sj] = T;
	Qm.push({ Si, Sj, S });
	while (!Qm.empty()) {
		int i = Qm.front()[0];
		int j = Qm.front()[1];
		int s = Qm.front()[2];
		Qm.pop();
		MechoGoTo(i + 1, j, s, Dm[i][j]);
		MechoGoTo(i - 1, j, s, Dm[i][j]);
		MechoGoTo(i, j + 1, s, Dm[i][j]);
		MechoGoTo(i, j - 1, s, Dm[i][j]);
	}
	return Dm[Ti][Tj] != INF;
}

int main() {
	scanf("%d %d", &N, &S);
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			Db[i][j] = INF;
			scanf(" %c", &A[i][j]);
			if (A[i][j] == 'H') {
				Db[i][j] = 0;
				Qb.push({ i, j });
			}
			else if (A[i][j] == 'M') {
				Si = i;
				Sj = j;
			}
			else if (A[i][j] == 'D') {
				Ti = i;
				Tj = j;
			}
		}
	}
	BeesBreadthFirstSearch();
	int lo = 0;
	int hi = N * N;
	while (lo < hi) {
		int mid = (lo + hi + 1) / 2;
		if (MechoBreadthFirstSearch(mid))
			lo = mid;
		else
			hi = mid - 1;
	}
	printf("%d\n", MechoBreadthFirstSearch(lo) ? lo : -1);
}

Compilation message (stderr)

mecho.cpp: In function 'int main()':
mecho.cpp:69:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |         scanf("%d %d", &N, &S);
      |         ~~~~~^~~~~~~~~~~~~~~~~
mecho.cpp:73:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |                         scanf(" %c", &A[i][j]);
      |                         ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 11 / 100