Submission #74491

#	Time	Username	Problem	Language	Result	Execution time	Memory
74491		JustInCase	Mecho (IOI09_mecho)	C++17	100 / 100	306 ms	11704 KiB

mecho

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

const int64_t MAX_N = 800;

const int64_t DELTA_ROWS[] = { -1, 0, 1, 0 };
const int64_t DELTA_COLS[] = { 0, 1, 0, -1 };

char board[MAX_N + 5][MAX_N + 5];
int64_t n, s, startR, startC, endR, endC, beeTimes[MAX_N + 5][MAX_N + 5];
int64_t mechoTimes[MAX_N + 5][MAX_N + 5];
vector< pair< int64_t, int64_t > > hives;

void PrecomputeBeeTimes() {
	queue< pair< int64_t, int64_t > > q;

	memset(beeTimes, -1, sizeof(beeTimes));
	for(auto &x : hives) {
		q.push(x);
		beeTimes[x.first][x.second] = 0;
	}

	while(!q.empty()) {
		int64_t r = q.front().first, c = q.front().second;
		int64_t time = beeTimes[r][c];
		q.pop();

		for(int64_t p = 0; p < 4; p++) {
			int64_t newR = r + DELTA_ROWS[p];
			int64_t newC = c + DELTA_COLS[p];

			if(newR >= 0 && newR < n && newC >= 0 && newC < n 
					&& board[newR][newC] == 'G' && beeTimes[newR][newC] == -1) {
				q.push({ newR, newC });
				beeTimes[newR][newC] = time + 1;
			}
		}
	}
}

bool Check(int64_t startTime) {
	queue< pair< int64_t, int64_t > > q;

	memset(mechoTimes, -1, sizeof(mechoTimes));
	mechoTimes[startR][startC] = startTime;
	
	if(startTime >= beeTimes[startR][startC]) {
		return false;
	}

	q.push({ startR, startC });

	while(!q.empty()) {
		int64_t r = q.front().first, c = q.front().second;
		int64_t nxtTime = mechoTimes[r][c] + 1;
		q.pop();
			
		if(r == endR && c == endC) {
			return true;
		}

		int64_t maxBeeTime;
		if(nxtTime % s == 0) {
			maxBeeTime = nxtTime + 1;
		}
		else {
			maxBeeTime = nxtTime;
		}
		
		for(int64_t p = 0; p < 4; p++) {
			int64_t newR = r + DELTA_ROWS[p];
			int64_t newC = c + DELTA_COLS[p];

			if(newR >= 0 && newR < n && newC >= 0 && newC < n 
					&& (board[newR][newC] == 'G' || board[newR][newC] == 'D')
					&& mechoTimes[newR][newC] == -1
					&& (beeTimes[newR][newC] >= maxBeeTime 
						|| beeTimes[newR][newC] < 0)) {
				q.push({ newR, newC });
				mechoTimes[newR][newC] = nxtTime;
			}
		}
	}

	return false;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n >> s;

	for(int64_t i = 0; i < n; i++) {
		for(int64_t j = 0; j < n; j++) {
			cin >> board[i][j];
		
			if(board[i][j] == 'M') {
				startR = i;
				startC = j;
				board[i][j] = 'G';
			}
			else if(board[i][j] == 'D') {
				endR = i;
				endC = j;
			}
			else if(board[i][j] == 'H') {
				hives.push_back({ i, j });
			}
		}
	}

	PrecomputeBeeTimes();

	for(int64_t i = 0; i < n; i++) {
		for(int64_t j = 0; j < n; j++) {
			beeTimes[i][j] *= s;
		}	
	}

	int64_t low = 0, high = MAX_N * MAX_N * MAX_N, ans = -1;
	while(low <= high) {
		int64_t mid = (low + high) / 2;

		if(Check(mid * s)) {
			low = mid + 1;
			ans = mid;
		}
		else {
			high = mid - 1;
		}
	}

	cout << ans << endl;
}

• Subtask 1: 100 / 100