Submission #366947

#	Time	Username	Problem	Language	Result	Execution time	Memory
366947		kostia244	Mecho (IOI09_mecho)	C++17	76 / 100	234 ms	6508 KiB

mecho

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2")
#include<bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
const int maxn = 808, C = 1;
using ll = long long;
int n, s;
char c[maxn][maxn];
array<int, 2> st, en;
int bdi[maxn][maxn];
vector<array<int, 2>> d {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
bool good(int x, int y) {
	return !(min(x, y) < 1 || max(x, y) > n) && c[x][y] != 'T'; 
}
void bees() {
	memset(bdi, -1, sizeof bdi);
	queue<array<int, 2>> q;
	auto add = [&](int x, int y, int d) {
		if(bdi[x][y] >= 0) return;
		if(c[x][y] == 'D') return;
		bdi[x][y] = d;
		q.push({x, y});
	};
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			if(c[i][j] == 'H') add(i, j, 0);
	while(!q.empty()) {
		auto [x, y] = q.front(); q.pop();
		for(auto [dx, dy] : d) {
			int tx = x+dx, ty = y+dy;
			if(good(tx, ty)) add(tx, ty, bdi[x][y]+1);
		}
	}
}
int dist[maxn][maxn];
bool check(int ti) {
	queue<array<int, 2>> q;
	memset(dist, -1, sizeof dist);
	auto add = [&](int x, int y, int d) {
		if(dist[x][y] >= 0) return;
		//cout << x << " " << y << " " << d << " | " << bdi[x][y] << endl;
		if(bdi[x][y] != -1 && ti + (d/s) >= bdi[x][y]) return;
		dist[x][y] = d;
		q.push({x, y});
	};
	add(st[0], st[1], 0);
	while(!q.empty()) {
		auto [x, y] = q.front(); q.pop();
		for(auto [dx, dy] : d) {
			int tx = x+dx, ty = y+dy;
			if(good(tx, ty)) add(tx, ty, dist[x][y]+1);
		}
	}
	return dist[en[0]][en[1]] >= 0;
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> s;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++) {
			cin >> c[i][j];
			if(c[i][j] == 'M') st = {i, j};
			if(c[i][j] == 'D') en = {i, j};
		}
	bees();
	
	if(!check(0)) return cout << -1, 0;
	int ans = 0;
	for(int i = 1<<12; i>>=1;) ans += i*check(ans+i);
	cout << ans << '\n';
}

• Subtask 1: 76 / 100