제출 #629694

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
629694		54skyxenon	Mecho (IOI09_mecho)	C++17	100 / 100	455 ms	6584 KiB

mecho

// https://oj.uz/problem/view/IOI09_mecho
 
#include <bits/stdc++.h>
using namespace std;

#define pii pair<int, int>
#define MAX_N 800

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

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

int mechox, mechoy, home_x, home_y;
vector<vector<bool>> bees_visited(MAX_N, vector<bool>(MAX_N));
vector<vector<int>> bees_time(MAX_N, vector<int>(MAX_N));
 
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;
}

// can Mecho eat for the given amount of time and still make it?
bool ok(int eating_time) {
    vector<vector<bool>> mecho_visited(n, vector<bool>(n));
	vector<vector<int>> mecho_time(n, vector<int>(n));
		
	// move Mecho
    queue<pii> q;
	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];
			/* 
			 * check if mecho reaces node[x][y] before the bees
			 * divide the time mecho takes to reach a node by s, since 
			 * mecho walks s steps at a time.
			 * substract the eating time from the time taken for the 
			 * bees to reach the node, because that time was used by 
			 * mecho for eating
			*/
			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;
				mecho_time[nx][ny] = mecho_time[x][y] + 1;
				q.push({nx, ny});
			}
		}
	}

	// check if mecho reached a node surrounding his cave before the bees
	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]) {
			return true;
		}
	}
    
    return false;
}

int bs(int lo, int hi) {
    if (lo > hi) {
        return -1;
    }

    int mid = (lo + hi) / 2;

    if (!ok(mid)) {
        return bs(lo, mid - 1);
    }
    else if (mid < hi && ok(mid + 1)) {
        return bs(mid + 1, hi);
    }
    else {
        return mid;
    }
}
 
int main() {
	cin >> n >> s;
	for (int i = 0; i < n; i++) {
		cin >> field[i];
	}
	
	// find x and y coordinates for for Mecho, the bees and the cave
	vector<pii> hives;
	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;
			}
		}
	}

    // move bees
    queue<pii> q;
	for (auto [hx, hy] : hives) {
		q.push({hx, hy});
		bees_visited[hx][hy] = 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;
			}
		}
	}
 
	// binary search on waiting time
    cout << bs(0, n * n) << "\n";
}

• Subtask 1: 100 / 100