Submission #646057

#	Time	Username	Problem	Language	Result	Execution time	Memory
646057		ymm	Mecho (IOI09_mecho)	C++17	100 / 100	170 ms	9564 KiB

mecho

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 810;
char forest[N][N];
int near_bee[N][N];
int bhi, bhj, bsi, bsj;
ll n, s;


bool can_go_bear(int i, int j)
{
	return 0 <= i && i < n && 0 <= j && j < n
	       && forest[i][j] != 'T';
}
bool can_go_bee(int i, int j)
{
	return 0 <= i && i < n && 0 <= j && j < n
	       && forest[i][j] != 'T' && forest[i][j] != 'D';
}

void bfs_bee()
{
	queue<pii> q;
	memset(near_bee, -1, sizeof(near_bee));
	Loop (i,0,n) Loop (j,0,n) {
		if (forest[i][j] == 'H') {
			near_bee[i][j] = 0;
			q.push({i, j});
		}
	}
	while (q.size()) {
		auto [i, j] = q.front();
		q.pop();
		int d = near_bee[i][j];
		for (auto [x_, y_] : {pii{0,1}, {0,-1}, {1,0}, {-1,0}}) {
			int x = i+x_, y = j+y_;
			if (!can_go_bee(x, y))
				continue;
			if (near_bee[x][y] != -1)
				continue;
			near_bee[x][y] = d+1;
			q.push({x, y});
		}
	}
}

void find_bear()
{
	Loop (i,0,n) Loop (j,0,n) {
		if (forest[i][j] == 'D') {
			bhi = i;
			bhj = j;
		}
		if (forest[i][j] == 'M') {
			bsi = i;
			bsj = j;
		}
	}
}

bool bfs_bear(int wait)
{
	if (wait >= near_bee[bsi][bsj])
		return 0;
	static ll dis[N][N];
	memset(dis, -1, sizeof(dis));
	queue<pii> q;
	q.push({bsi, bsj});
	dis[bsi][bsj] = (ll)wait * s;
	while (q.size()) {
		auto [i, j] = q.front();
		q.pop();
		ll d = dis[i][j];
		for (auto [x_, y_] : {pii{0,1}, {0,-1}, {1,0}, {-1,0}}) {
			int x = i+x_, y = j+y_;
			if (!can_go_bear(x, y))
				continue;
			if (near_bee[x][y] != -1
			    && near_bee[x][y] <= (d+1)/s)
				continue;
			if (dis[x][y] != -1)
				continue;
			dis[x][y] = d+1;
			q.push({x, y});
		}
	}
	return dis[bhi][bhj] != -1;
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n >> s;
	Loop (i,0,n)
		cin >> forest[i];
	bfs_bee();
	find_bear();
	int l = -1, r = near_bee[bsi][bsj]-1;
	while (l < r) {
		int mid = (l+r+1)/2;
		if (bfs_bear(mid))
			l = mid;
		else
			r = mid-1;
	}
	cout << l << '\n';
}

• Subtask 1: 100 / 100