Submission #747793

#	Time	Username	Problem	Language	Result	Execution time	Memory
747793		AverageAmogusEnjoyer	Mecho (IOI09_mecho)	C++17	30 / 100	742 ms	6592 KiB

mecho

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T>
using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define all(x) x.begin(), x.end() 
#define sz(x) (int) x.size()
#define pb push_back
#define ll long long
#define nl '\n'

/*

Mecho can only walk on grass and cannot go through trees or hives, and he can make at most S steps per minute.
every minute
he eats or 
he leaves immediately and takes up to S steps through the forest as described above

bees spread to grassy cells

trees = no one can go there

m = mecho, grassy cells => i will replace with g

g = grassy

d = mecho home; bees cannot go / pass here

h = hive

*/

const int N = 810;

char grid[N][N];
int stepsMecho[N][N], stepsBee[N][N];
int n, s;
array<int, 2> Mecho, MechoHouse;
vector<array<int, 2>> Bee;
vector<array<int,2>> moves = {{-1,0},{1,0},{0,-1},{0,1}};

struct m{
	bool isMecho;
	int x,y;
};

bool good(int x, int y) {
	return 0 <= x && x < n && 0 <= y && y < n && grid[x][y] != 'T';
}

bool isHome(int x, int y) {
	return x == MechoHouse[0] && y == MechoHouse[1];
}

void debug() {
	cout << "Mecho: " << nl;
	for (int i=0;i<n;i++) {
		for (int j=0;j<n;j++) {
			cout << stepsMecho[i][j] << " ";
		}
		cout << nl;
	}
	cout << "Bees: " << nl;
	for (int i=0;i<n;i++) {
		for (int j=0;j<n;j++) {
			cout << stepsBee[i][j] << " ";
		}
		cout << nl;
	}
}

bool bs(int steps) {
	memset(stepsMecho,-1,sizeof(stepsMecho));
	memset(stepsBee,-1,sizeof(stepsBee));
	queue<m> q, q2;
	q2.push(m{true,Mecho[0],Mecho[1]});
	stepsMecho[Mecho[0]][Mecho[1]] = 0;
	for (auto [x,y]:Bee) {
		q.push(m{false,x,y});
		stepsBee[x][y]=0;
	}
	while(!q.empty()) {
		m v = q.front(); q.pop();
		if (stepsBee[v.x][v.y] == steps) { q2.push(v); continue; }
 		for (auto [addx,addy]: moves) {
			int nx = v.x + addx, ny = v.y + addy;
			if (good(nx,ny) && !isHome(nx,ny) && stepsBee[nx][ny] == -1) {
				q.push(m{false,nx,ny});
				stepsBee[nx][ny] = stepsBee[v.x][v.y]+1;
			}
		}
	}
	for (int i=0;i<n;i++)
		for (int j=0;j<n;j++)
			if (stepsBee[i][j] != -1)
				stepsBee[i][j] = 0;
	while(!q2.empty()) {
		m v = q2.front(); q2.pop();
		if (v.isMecho) {
			if (stepsBee[v.x][v.y] != -1 && stepsBee[v.x][v.y] <= (stepsMecho[v.x][v.y]+s-1)/s) { continue; }
			for (auto [addx,addy]: moves) {
				int nx = v.x + addx, ny = v.y + addy;
				if (good(nx,ny) && stepsMecho[nx][ny] == -1 && (stepsBee[nx][ny] == -1 || stepsBee[nx][ny] > (stepsMecho[v.x][v.y]+s)/s)) {
					if (isHome(nx,ny)) { return 1; }
					stepsMecho[nx][ny] = stepsMecho[v.x][v.y]+1;
					q2.push(m{true,nx,ny});
				}
			}
		} else {
			for (auto [addx,addy]: moves) {
				int nx = v.x + addx, ny = v.y + addy;
				if (good(nx,ny) && !isHome(nx,ny) && stepsBee[nx][ny] == -1) {
					q2.push(m{false,nx,ny});
					stepsBee[nx][ny] = stepsBee[v.x][v.y]+1;
				}
			}
		}
	}
	return 0;
}

signed main() {
	// freopen(".in", "r", stdin);
	// freopen(".out", "w", stdout);
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> s;
	for (int i=0;i<n;i++)
		for (int j=0;j<n;j++) {
			cin >> grid[i][j];
			if (grid[i][j]=='M') {
				grid[i][j] = 'G';
				Mecho = {i,j};
			}
			if (grid[i][j]=='H') {
				Bee.pb({i,j});
			}
			if (grid[i][j]=='D') {
				MechoHouse = {i,j};
			}
		}
	int lo = 0, hi = 1e9;
	while(lo<=hi) {
		int mid = (lo+hi)/2;
		if (bs(mid)) {
			lo = mid + 1;
		} else {
			if (mid==0) {
				cout << -1;
				return 0;
			}
			hi = mid - 1;
		}
	}
	cout << lo;
}

• Subtask 1: 30 / 100