Submission #153020

#	Time	Username	Problem	Language	Result	Execution time	Memory
153020		tselmegkh	Mecho (IOI09_mecho)	C++14	20 / 100	1092 ms	7012 KiB

mecho

#include<bits/stdc++.h>
using namespace std;

const int N = 805, inf = 1e9;
string a[N];
int d[N][N], dis[N][N], n, s;
bool vis[N][N];
pair<int, int> st, en;
int mx = 0;
int movex[] = {1, 0, -1, 0};
int movey[] = {0, 1, 0, -1};

void fill(){
	for(int i = 0; i < 801; i++){
		for(int j = 0; j < 801; j++){
			d[i][j] = inf;
		}
	}
}

bool check(int i, int j, bool which){
	if(which == 1)
		{
		if(i >= 0 && i < n && j >= 0 && j < n && (a[i][j] == 'G' || a[i][j] == 'D') && !vis[i][j]){
			return 1;
		}
		return 0;
	}
	else{
		if(i >= 0 && i < n && j >= 0 && j < n && a[i][j] == 'G' && !vis[i][j]){
			return 1;
		}
		return 0;
	}
}

void bfs(int i, int j){
	memset(vis, 0, sizeof vis);
	memset(dis, 0, sizeof dis);
	queue<pair<int, int>> q;
	dis[i][j] = 0;
	vis[i][j] = 1;
	q.push({i, j});

	while(!q.empty()){
		pair<int, int> u = q.front(); q.pop();

		for(int i1 = 0; i1 < 4; i1++){
			int x = movex[i1], y = movey[i1];
			if(check(u.first + x, u.second + y, 0)){
				vis[u.first + x][u.second + y] = 1;
				dis[u.first + x][u.second + y] = dis[u.first][u.second] + 1;
				d[u.first + x][u.second + y] = min(d[u.first + x][u.second + y], dis[u.first + x][u.second + y]);
				q.push({u.first + x, u.second + y});
				mx = max(mx, d[u.first + x][u.second + y]);
			}
		}
	}
}

bool possible(int x){
	int cur = x;
	memset(vis, 0, sizeof vis);
	queue<pair<pair<int, int>, pair<int,int>>> q;

	q.push({{st.first, st.second}, {cur, s}});
	vis[st.first][st.second] = 1;

	while(!q.empty()){
		auto k = q.front(); q.pop();
		int u = k.first.first, v = k.first.second, chargesleft = k.second.second;
		int now = k.second.first;

		for(int i = 0; i < 4; i++){
			if(check(u + movex[i], v + movey[i], 1)){
				if(d[u + movex[i]][v + movey[i]] > now){
					if(chargesleft > 1){
						q.push({{u + movex[i], v + movey[i]}, {now, chargesleft - 1}});
					}else{
						q.push({{u + movex[i], v + movey[i]}, {now + 1, s}});
					}
					vis[u + movex[i]][v + movey[i]] = 1;
				}
			}
		}
	}
	/*cout << "x : " << x << '\n';
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			cout << vis[i][j];
		}
		cout << '\n';
	}*/
	if(vis[en.first][en.second])return 1;
	return 0;
}
int main(){
	cin >> n >> s;
	fill();

	for(int i = 0; i < n; i++){
		cin >> a[i];
	}
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			if(a[i][j] == 'H'){
				bfs(i, j);
			}
			if(a[i][j] == 'M'){
				st.first = i;
				st.second = j;
			}
			if(a[i][j] == 'D'){
				en.first = i;
				en.second = j;
			}
		}
	}
	/*for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			if(d[i][j] != inf)cout << d[i][j];
			else cout << 0;
		}
		cout << '\n';
	}*/

	int l = 0, r = mx;

	while(l != r){
		int mid = l + (r - l + 1) / 2;
		if(possible(mid)){
			l = mid;
		}else{
			r = mid - 1;
		}
	}
	cout << l << '\n';
}

• Subtask 1: 20 / 100