Submission #1186713

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186713		peteza	Mecho (IOI09_mecho)	C++20	100 / 100	599 ms	5120 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using pip = pair<int, pii>;

int n, k;
char mp[805][805];
int si, sj, ei, ej;
int l = 0, r = 805*805, mid;
bool vismech[805][805], visbee[805][805], visfake[805][805];
vector<pii> fakebees;
int di[4] = {0, 0, 1, -1}, dj[4] = {1, -1, 0, 0};
queue<pip> qbee, qmech;

bool doable(int start) {
	memset(vismech, 0, sizeof vismech);
	memset(visbee, 0, sizeof visbee);
	while(!qbee.empty()) qbee.pop();
	while(!qmech.empty()) qmech.pop();
	//bees move first, start times
	for(int i=0;i<n;i++) {
		for(int j=0;j<n;j++) {
			if(mp[i][j] == 'H') {
				qbee.emplace(0, make_pair(i, j));
			}
		}
	}
	while(!qbee.empty() && qbee.front().first <= start) {
		auto e = qbee.front(); qbee.pop();
		int ci = e.second.first, cj = e.second.second;
		if(visbee[ci][cj]) continue;
		visbee[ci][cj] = 1;
		for(int dir = 0; dir < 4; dir ++) {
			int ni = ci + di[dir], nj = cj + dj[dir];
			if(ni < 0 || nj < 0 || ni >= n || nj >= n) continue;
			if(mp[ni][nj] == 'T' || mp[ni][nj] == 'D') continue;
			qbee.emplace(e.first+1, make_pair(ni, nj));
		}
	}
	qmech.emplace(0, make_pair(si, sj));
	/*cout << "---\n";
	for(int i=0;i<n;i++) {
		for(int j=0;j<n;j++) cout << visbee[i][j];
		cout << '\n';
	}
	cout << "----\n";*/
	//now mecho starts moving
	for(int cr=0;cr<=n*n;cr++) {
		fakebees.clear();
		int curbeecnt = (qbee.empty() ? -69 : qbee.front().first);
		while(!qbee.empty() && qbee.front().first == curbeecnt) {
			auto e = qbee.front(); qbee.pop();
			int ci = e.second.first, cj = e.second.second;
			if(visbee[ci][cj]) continue;
			visbee[ci][cj] = 1; fakebees.emplace_back(ci, cj);
			for(int dir = 0; dir < 4; dir ++) {
				int ni = ci + di[dir], nj = cj + dj[dir];
				if(ni < 0 || nj < 0 || ni >= n || nj >= n) continue;
				if(mp[ni][nj] == 'T' || mp[ni][nj] == 'D') continue;
				qbee.emplace(e.first+1, make_pair(ni, nj));
			}
		}
		for(auto &e:fakebees) {visbee[e.first][e.second] = 0; visfake[e.first][e.second] = 1;}
		while(!qmech.empty() && qmech.front().first <= 1ll*(cr+1)*k) {
			auto e = qmech.front(); qmech.pop();
			int ci = e.second.first, cj = e.second.second;
			if(visbee[ci][cj]) continue;
			if(vismech[ci][cj]) continue;
			vismech[ci][cj] = 1;
			if(e.first == 1ll*(cr+1)*k && visfake[ci][cj]) continue;
			for(int dir = 0; dir < 4; dir++) {
				int ni = ci+di[dir], nj = cj+dj[dir];
				if(ni < 0 || nj < 0 || ni >= n || nj >= n) continue;
				if(mp[ni][nj] == 'T') continue;
				qmech.emplace(e.first+1, make_pair(ni, nj));
			}
		}
		for(auto &e:fakebees) {visbee[e.first][e.second] = 1; visfake[e.first][e.second] = 0;}
	}
	/*cout << start << '\n';
	for(int i=0;i<n;i++) {
		for(int j=0;j<n;j++) cout << vismech[i][j];
		cout << '\n';
	}*/
	return vismech[ei][ej];
}

int main() {
	cin.tie(0) -> sync_with_stdio(0);
	cin >> n >> k;
	for(int i=0;i<n;i++) {
		for(int j=0;j<n;j++) {
			cin >> mp[i][j];
			if(mp[i][j] == 'M') {
				si = i; sj = j;
			}
			if(mp[i][j] == 'D') {
				ei = i; ej = j;
			}
		}
	}
	//for(int i=0;i<=10;i++) doable(i); cout << '\n';
	while(l <= r) {
		mid = (l+r) >> 1;
		if(doable(mid)) l = mid+1;
		else r = mid-1;
	}
	cout << r;
}

• Subtask 1: 100 / 100