Submission #599848

#	Time	Username	Problem	Language	Result	Execution time	Memory
599848		alexz1205	Mecho (IOI09_mecho)	C++14	22 / 100	1100 ms	8568 KiB

mecho

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

int n, s, dist[802][802], dist2[802][802], dist3[802][802];
bool req[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] = dist2[x][y] = -1;
			req[x][y] = 1;
			char c;
			cin >> c;
			switch (c){
				case 'T':
					dist[x][y] = dist2[x][y] = req[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] = req[x][y] = dist2[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));
		}
	}
}

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

int main() {
	setup();
	calc();
	mecho();
	for (int x = 0; x <= n+1; x ++){
		for (int y = 0; y <= n+1; y ++){
			dist3[x][y] = (dist[x][y] - dist2[x][y] >= 0 ? (dist[x][y] - dist2[x][y]) / s : -1);
		}
	}
	set<pair<int, pair<int, int> > > pri;
	pri.insert(make_pair(dist3[beg.first][beg.second], beg));
	while (!pri.empty()){
		int m = pri.rbegin()->first;
		int i = pri.rbegin()->second.first, j = pri.rbegin()->second.second;
		pri.erase(--pri.end());
		if (i == home.first && j == home.second){
			cout << m << endl;
			break;
		}
		if (req[i-1][j]){
			req[i-1][j] = 0;
			pri.insert(make_pair(min(m, dist3[i-1][j]), make_pair(i-1, j)));
		}
		if (req[i][j-1]){
			req[i][j-1] = 0;
			pri.insert(make_pair(min(m, dist3[i][j-1]), make_pair(i, j-1)));
		}
		if (req[i+1][j]){
			req[i+1][j] = 0;
			pri.insert(make_pair(min(m, dist3[i+1][j]), make_pair(i+1, j)));
		}
		if (req[i][j+1]){
			req[i][j+1] = 0;
			pri.insert(make_pair(min(m, dist3[i][j+1]), make_pair(i, j+1)));
		}
	}
	return 0;
}

Compilation message (stderr)

mecho.cpp: In function 'void setup()':
mecho.cpp:32:43: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   32 |      dist[x][y] = req[x][y] = dist2[x][y] = 0;
      |                               ~~~~~~~~~~~~^~~

• Subtask 1: 22 / 100