Submission #1191523

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191523		pete555	Mecho (IOI09_mecho)	C++20	100 / 100	171 ms	9180 KiB

mecho

#include<bits/stdc++.h>
using namespace std;

#define pi pair<int,int>
#define ll long long
#define pb push_back
#define pf push_front

void fileIO(string filename) {
	freopen((filename + ".in").c_str(), "r", stdin);
	freopen((filename + ".out").c_str(), "w", stdout);
}

const int N = 1000;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};

vector<vector<int>> d_bees(N, vector<int>(N, -1));
char g[N][N];

int home_x, home_y;
int mecho_x, mecho_y;
int n, s;

bool inside(int x, int y){
	return (0 <= x and x < n and 0 <= y and y < n) and (g[x][y] == 'G' or g[x][y] == 'M');	
}
bool reachable(int t_mecho, int t_bees){
	return t_mecho / s < t_bees;
}

queue<pi> q;

int main()
{
	cin.tie(0)->sync_with_stdio(false);
	//fileIO("");
	cin >> n >> s;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			cin >> g[i][j];
			if(g[i][j] == 'D'){
				home_x = i;
				home_y = j;
			}
			if(g[i][j] == 'M'){
				mecho_x = i;
				mecho_y = j;
			}
			if(g[i][j] == 'H'){
				d_bees[i][j] = 0;
				q.push({i, j});
			}
		}
	}
	//calculating d_bees
	while(q.size()){
		const auto &[x, y] = q.front();
		q.pop();
		for(int i = 0; i < 4; i++){
			int nx = x + dx[i];
			int ny = y + dy[i];
			if(inside(nx, ny) and d_bees[nx][ny] == -1){
				d_bees[nx][ny] = d_bees[x][y] + 1;
				q.push({nx, ny});
			}
		}
	}
	//binary search on largest waiting time
	int l = -1, r = n * n;
	while(l < r){
		int t_waiting = (l + r + 1) / 2;

		vector<vector<int>> d_mecho(N, vector<int>(N, -1));
		d_mecho[mecho_x][mecho_y] = 0;
		q.push({mecho_x, mecho_y});
		if(d_bees[mecho_x][mecho_y] != -1 and d_bees[mecho_x][mecho_y] <= t_waiting){
			d_mecho[mecho_x][mecho_y] = -1;
			q.pop();
		}
		while(q.size()){
			const auto &[x, y] = q.front();
			q.pop();
			for(int i = 0; i < 4; i++){
				int nx = x + dx[i];
				int ny = y + dy[i];
				if(inside(nx, ny) and (d_bees[nx][ny] == -1 or reachable(d_mecho[x][y] + 1, d_bees[nx][ny] - t_waiting)) and d_mecho[nx][ny] == -1){
					d_mecho[nx][ny] = d_mecho[x][y] + 1;
					q.push({nx, ny});
				}
			}
		}

		bool can = false;
		for(int i = 0; i < 4; i++){
			int nx = home_x + dx[i];
			int ny = home_y + dy[i];
			if(inside(nx, ny) and d_mecho[nx][ny] != -1) can = true;
		}
		if(can) l = t_waiting;
		else r = t_waiting - 1;
	}
	cout << l << '\n';
}

Compilation message (stderr)

mecho.cpp: In function 'void fileIO(std::string)':
mecho.cpp:10:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |         freopen((filename + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mecho.cpp:11:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |         freopen((filename + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100