Submission #713175

#	Time	Username	Problem	Language	Result	Execution time	Memory
713175		ismayil	Mecho (IOI09_mecho)	C++17	100 / 100	268 ms	21620 KiB

mecho

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int INF = 0x3f3f3f3f;
char grid[801][801];
ll dis_b[801][801], color_b[801][801];
ll color[801][801], dis[801][801];
ll dx[4] = {0, 0, 1, -1};
ll dy[4] = {1, -1, 0, 0};
ll n, s;
pair<ll, ll> finish;
bool valid(ll i, ll j){
	return (0 <= i && i < n && 0 <= j && j < n);
}
void bfs_b(queue<pair<ll, ll>> &q){
	while(!q.empty()){
		ll x = q.front().first, y = q.front().second;
		q.pop();
		for(ll i = 0; i < 4; i++){
			if(valid(x + dx[i], y + dy[i]) && !color_b[x + dx[i]][y + dy[i]] && 
			(grid[x + dx[i]][y + dy[i]] == 'G' || grid[x + dx[i]][y + dy[i]] == 'M')){
				dis_b[x + dx[i]][y + dy[i]] = dis_b[x][y] + 1;
				color_b[x + dx[i]][y + dy[i]] = 1;
				q.push({x + dx[i], y + dy[i]});
			}
		} 
	}
}
bool bfs_m(ll i, ll j, ll t){
	memset(color, 0, sizeof(color));
	memset(dis, 0, sizeof(dis));
	dis[i][j] = t;
	color[i][j] = 1;
	if(dis[i][j] >= dis_b[i][j] * s) return false;
	queue<pair<ll, ll>> q;
	q.push({i, j});
	while(!q.empty()){
		ll x = q.front().first, y = q.front().second;
		q.pop();
		for(ll i = 0; i < 4; i++){
			if(valid(x + dx[i], y + dy[i]) && !color[x + dx[i]][y + dy[i]] &&
			(dis[x][y] + 1 < dis_b[x + dx[i]][y + dy[i]] * s || grid[x + dx[i]][y + dy[i]] == 'D') && 
			(grid[x + dx[i]][y + dy[i]] == 'G' || grid[x + dx[i]][y + dy[i]] == 'D')){
				dis[x + dx[i]][y + dy[i]] = dis[x][y] + 1;
				color[x + dx[i]][y + dy[i]] = 1;
				q.push({x + dx[i], y + dy[i]});
			}
		} 
	}
	return color[finish.first][finish.second];
}

int main() {
	ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
	cin>>n>>s;
	if(n == 1){
		cout<<-1;
		return 0;
	}
	queue<pair<ll, ll>> b, m;
	for(ll i = 0; i < n; i++){
		for(ll j = 0; j < n; j++){
			cin>>grid[i][j];
			if(grid[i][j] == 'H'){
				b.push({i, j});
				color_b[i][j] = 1;
				dis_b[i][j] = 0;
			}else if(grid[i][j] == 'M'){
				m.push({i, j});
			}else if(grid[i][j] == 'D'){
				finish = {i, j};
			}
		}
	}
	bfs_b(b);
	if(!bfs_m(m.front().first, m.front().second, 0)){
		cout<<-1;
		return 0;
	}
	ll l = 0, r = 2e9;
	ll ans = 0;
	while(l <= r){
		ll mid = (l + r) / 2;
		if(bfs_m(m.front().first, m.front().second, s * mid)){
			l = mid + 1;
			ans = max(ans, mid);
		}else r = mid - 1;
	}
	cout<<ans;
}
 

• Subtask 1: 100 / 100