Submission #599809

#	Time	Username	Problem	Language	Result	Execution time	Memory
599809		alexz1205	Mecho (IOI09_mecho)	C++14	2 / 100	1100 ms	3956 KiB

mecho

#include <iostream>
#include <vector>
using namespace std;

int n, s, dist[802][802];
pair<int, int> beg, home;
vector<pair<int, int> > hives;

void setup(){
	cin >> n >> s;
	for (int x = 1; x <= n; x ++){
		for (int y = 1; y <= n; y ++){
			dist[x][y] = -1;
			char c;
			cin >> c;
			switch (c){
				case 'T':
					dist[x][y] = 0;
					break;
				case 'G':
					break;
				case 'M':
					beg = make_pair(x, y);
					break;
				case 'D':
					home = make_pair(x, y);
					break;
				case 'H':
					dist[x][y] = 0;
					hives.push_back(make_pair(x, y));
					break;
			}
		}
	}
	for (int x = 0; x <= n+1; x ++){
		dist[x][0] = dist[0][x] = dist[n+1][x] = dist[x][n+1] = 0;
	}
}

void calc(){
	vector<pair<int, int> > que = hives;
	while (!que.empty()){
		int i = que.front().first, j = que.front().second;
		que.erase(que.begin());
		if (dist[i-1][j] == -1){
			dist[i-1][j] = dist[i][j] + s;
			que.push_back(make_pair(i-1, j));
		}
		if (dist[i+1][j] == -1){
			dist[i+1][j] = dist[i][j] + s;
			que.push_back(make_pair(i+1, j));
		}
		if (dist[i][j-1] == -1){
			dist[i][j-1] = dist[i][j] + s;
			que.push_back(make_pair(i, j-1));
		}
		if (dist[i][j+1] == -1){
			dist[i][j+1] = dist[i][j] + s;
			que.push_back(make_pair(i, j+1));
		}
	}
}

bool pos(int mid){
	vector<pair<pair<int, int>, int> > que;
	que.push_back(make_pair(beg, mid));
	while (!que.empty()){
		int i = que.front().first.first, j = que.front().first.second;
		int d = que.front().second;
		que.erase(que.begin());
		if (i == home.first && j == home.second){
			return true;
		}
		if (i == home.first-1 && j == home.second){
			return true;
		}
		if (i == home.first && j == home.second-1){
			return true;
		}
		if (i == home.first+1 && j == home.second){
			return true;
		}
		if (i == home.first && j == home.second+1){
			return true;
		}
		if (dist[i-1][j] > d){
			que.push_back(make_pair(make_pair(i-1, j), d+1));
		}
		if (dist[i+1][j] > d){
			que.push_back(make_pair(make_pair(i+1, j), d+1));
		}
		if (dist[i][j-1] > d){
			que.push_back(make_pair(make_pair(i, j-1), d+1));
		}
		if (dist[i][j+1] > d){
			que.push_back(make_pair(make_pair(i, j+1), d+1));
		}
	}
	return false;
}

int main() {
	setup();
	calc();
	int lo = 0, hi = dist[beg.first][beg.second]/s+1;
	while (lo <= hi){
		int mid = lo + (hi-lo+1)/2;
		if (pos(s*mid)){
			lo = mid+1;
		}else {
			hi = mid-1;
		}
	}
	cout << lo-1 << endl;
	return 0;
}

• Subtask 1: 2 / 100