Submission #611893

#	Time	Username	Problem	Language	Result	Execution time	Memory
611893		Belgutei	Mecho (IOI09_mecho)	C++17	79 / 100	171 ms	10068 KiB

mecho

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define ff first
#define ss second
#define pb push_back
#define mk make_pair
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

int n,m;
int b[805][806];
queue<pair<int,int> > q;
int stx, sty;
int cnt[805][805];
int tmp[805][805];
bool check = 0;
char ch[805][805];
bool visited[805][805];

int main() {
	IOS
	cin >> n >> m;
	for(int i = 1; i <= n; i ++) {
		for(int j = 1; j <= n; j ++) {
			cin >> ch[i][j];
			if(ch[i][j] == 'H') {
				b[i][j] = 1;
				q.push({i,j});
			}
			if(ch[i][j] == 'M') {
				stx = i;
				sty = j;
			}
		}
	}
	while(q.size() > 0) {
		int x = q.front().ff;
		int y = q.front().ss;
		q.pop();
		if(x > 1 && b[x - 1][y] == 0 && ch[x - 1][y] != 'T' && ch[x - 1][y] != 'D') {
			q.push({x - 1, y});
			b[x - 1][y] = b[x][y] + 1;
		}
		if(x < n && b[x + 1][y] == 0 && ch[x + 1][y] != 'T' && ch[x + 1][y] != 'D') {
			q.push({x + 1, y});
			b[x + 1][y] = b[x][y] + 1;
		}
		if(y > 1 && b[x][y - 1] == 0 && ch[x][y - 1] != 'T' && ch[x][y - 1] != 'D') {
			q.push({x, y - 1});
			b[x][y - 1] = b[x][y] + 1;
		}
		if(y < n && b[x][y + 1] == 0 && ch[x][y + 1] != 'T' && ch[x][y + 1] != 'D') {
			q.push({x, y + 1});
			b[x][y + 1] = b[x][y] + 1;
		}		
	}
	for(int i = 1; i <= n; i ++) {
		for(int j = 1; j <= n; j ++) {
			if(b[i][j] == 0) b[i][j] = 1e9;
			else b[i][j] --;
		}
	} 

	int l = 0;
	int r = n * n;
	while(l < r) {
		int mid = (l + r + 1) / 2;
		memset(cnt, -1, sizeof(cnt));
		memset(visited, 0, sizeof(visited));
		while(q.size() > 0) q.pop();
		//
		if(mid >= b[stx][sty]) {
			r = mid - 1;
			continue;
		}
		q.push({stx, sty});
		cnt[stx][sty] = mid;	
		tmp[stx][sty] = m;
		visited[stx][sty] = 1;
		bool ok = 0;
		//
		while(q.size() > 0) {
			int x = q.front().ff;
			int y = q.front().ss;
			q.pop();
			if(ch[x][y] == 'D') {
				ok = 1;
				break;
			}
			int num = cnt[x][y];
			int move = tmp[x][y];
			if(move == m) {
				if(visited[x][y] == 0) continue;
				num ++;
				move = 0;
			}
			move ++;
			//
			if(x > 1 && num <= b[x - 1][y] && cnt[x - 1][y] == -1 && ch[x - 1][y] != 'T') {
				cnt[x - 1][y] = num;
				tmp[x - 1][y] = move;
				q.push({x - 1, y});
				if(num < b[x - 1][y]) visited[x - 1][y] = 1;
			}
			if(x < n && num <= b[x + 1][y] && cnt[x + 1][y] == -1 && ch[x + 1][y] != 'T') {
				cnt[x + 1][y] = num;
				tmp[x + 1][y] = move;
				q.push({x + 1, y});
				if(num < b[x + 1][y]) visited[x + 1][y] = 1;
			}
			if(y > 1 && num <= b[x][y - 1] && cnt[x][y - 1] == -1 && ch[x][y - 1] != 'T') {
				cnt[x][y - 1] = num;
				tmp[x][y - 1] = move;
				q.push({x, y - 1});
				if(num < b[x][y - 1]) visited[x][y - 1] = 1;
			}
			if(y < n && num <= b[x][y + 1] && cnt[x][y + 1] == -1 && ch[x][y + 1] != 'T') {
				cnt[x][y + 1] = num;
				tmp[x][y + 1] = move;
				q.push({x, y + 1});
				if(num < b[x][y + 1]) visited[x][y + 1] = 1;
			}
			
		}	
		if(ok == 1) {
			check = 1;
			l = mid;
		}
		else r = mid - 1;

	}
	if(check == 1){
		cout << l;
	} 
	else cout << -1;
}

• Subtask 1: 79 / 100