Submission #599779

#	Time	Username	Problem	Language	Result	Execution time	Memory
599779		alexz1205	Mecho (IOI09_mecho)	C++14	2 / 100	1096 ms	4424 KiB

mecho

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

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

void setup(){
	cin >> n >> s;
	for (int x = 0; x < n; x ++){
		for (int y = 0; 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;
			}
		}
	}
}

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 (i != 0){
			if (dist[i-1][j] == -1){
				dist[i-1][j] = dist[i][j] + s;
				que.push_back(make_pair(i-1, j));
			}
		}
		if (i != n-1){
			if (dist[i+1][j] == -1){
				dist[i+1][j] = dist[i][j] + s;
				que.push_back(make_pair(i+1, j));
			}
		}
		if (j != 0){
			if (dist[i][j-1] == -1){
				dist[i][j-1] = dist[i][j] + s;
				que.push_back(make_pair(i, j-1));
			}
		}
		if (j != n-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));
//	cout << beg.first << " " << beg.second << endl;
	while (!que.empty()){
		int i = que.front().first.first, j = que.front().first.second;
		int d = que.front().second;
//		cout << i << " " << j << " " << d << endl;
		que.erase(que.begin());
		if (i == home.first && j == home.second){
			return true;
		}
		if (i != 0){
			if (dist[i-1][j] > d){
				que.push_back(make_pair(make_pair(i-1, j), d+1));
			}
		}
		if (i != n-1){
			if (dist[i+1][j] > d){
				que.push_back(make_pair(make_pair(i+1, j), d+1));
			}
		}
		if (j != 0){
			if (dist[i][j-1] > d){
				que.push_back(make_pair(make_pair(i, j-1), d+1));
			}
		}
		if (j != n-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