Submission #1196208

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196208		rcll	Mecho (IOI09_mecho)	C++20	100 / 100	484 ms	6828 KiB

mecho

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

const int MAX_N=800;
vector<string> field(MAX_N);
int n,s;

bool valid_sq(int x,int y) {
	return x >= 0 && x<n && y >= 0 && y<n &&
	       (field[x][y]=='G' || field[x][y]=='M');
}

bool mecho_reached(int mecho_dis,int bees_dis) { 
    return mecho_dis/s<bees_dis; 
}

int main() {
	cin >> n >> s;
	for (int i=0; i<n; i++) { 
        cin >> field[i]; 
    }
	vector<pair<int,int>> hives;
	int mechox,mechoy,home_x,home_y;
	for (int i=0; i<n; i++) {
		for (int j=0; j<n; j++) {
			if (field[i][j]=='M') {
				mechox=i;
				mechoy=j;
			} else if (field[i][j]=='H') {
				hives.push_back({i,j});
			} else if (field[i][j]=='D') {
				home_x=i;
				home_y=j;
			}
		}
	}
	int dx[]={-1,0,1,0};
	int dy[]={0,-1,0,1};
	int l=0;
	int r=n * n;
	while (l <= r) {
		vector<vector<bool>> bees_visited(n,vector<bool>(n));
		vector<vector<bool>> mecho_visited(n,vector<bool>(n));
		vector<vector<int>> bees_time(n,vector<int>(n));
		vector<vector<int>> mecho_time(n,vector<int>(n));
		queue<pair<int,int>> q;
		int eating_time=(l+r)/2;
		for (auto i:hives) {
			q.push({i.first,i.second});
			bees_visited[i.first][i.second]=true;
		}
		while (!q.empty()) {
			int x=q.front().first,y=q.front().second;
			q.pop();
			for (int i=0; i<4; i++) {
				int nx=x+dx[i],ny=y+dy[i];
				if (valid_sq(nx,ny) && !bees_visited[nx][ny]) {
					bees_time[nx][ny]=bees_time[x][y]+1;
					q.push({nx,ny});
					bees_visited[nx][ny]=true;
				}
			}
		}
		q.push({mechox,mechoy});
		mecho_visited[mechox][mechoy]=true;
		if (bees_time[mechox][mechoy] <= eating_time) { 
            q.pop(); 
        }
		while (!q.empty()) {
			int x=q.front().first,y=q.front().second;
			q.pop();
			for (int i=0; i<4; i++) {
				int nx=x+dx[i],ny=y+dy[i];
				if (valid_sq(nx,ny) && !mecho_visited[nx][ny] &&
				    mecho_reached(mecho_time[x][y]+1,
				                  bees_time[nx][ny]-eating_time)) {
					mecho_visited[nx][ny]=true;
					q.push({nx,ny});
					mecho_time[nx][ny]=mecho_time[x][y]+1;
				}
			}
		}
		bool reached=false;
		for (int i=0; i<4; i++) {
			int nx=home_x+dx[i],ny=home_y+dy[i];
			if (valid_sq(nx,ny) &&
			    mecho_reached(mecho_time[nx][ny],bees_time[nx][ny]-eating_time) &&
			    mecho_visited[nx][ny]) {
				reached=true;
			}
		}
		if (reached) {
			l=eating_time+1;
		} else {
			r=eating_time-1;
		}
	}
	cout << l-1 << '\n';
}

• Subtask 1: 100 / 100