Submission #1193220

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193220		mehmetkagan	Mecho (IOI09_mecho)	C++20	21 / 100	230 ms	11208 KiB

mecho

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

const int INF = 1e9;
const int MAXN = 805;

int n, s;
char grid[MAXN][MAXN];
int bee_time[MAXN][MAXN]; // time bees reach each cell
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
pii mecho, home;

bool in_bounds(int x, int y) {
    return x >= 0 && y >= 0 && x < n && y < n;
}

void bfs_bees() {
    queue<pii> q;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            bee_time[i][j] = INF;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (grid[i][j] == 'H') {
                bee_time[i][j] = 0;
                q.push({i, j});
            }

    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            if (in_bounds(nx, ny) && (grid[nx][ny] == 'G' || grid[nx][ny] == 'M' || grid[nx][ny] == 'D') && bee_time[nx][ny] == INF) {
                bee_time[nx][ny] = bee_time[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }
}

bool can_escape(int wait_time) {
    queue<tuple<int, int, int>> q;
    vector<vector<int>> visited(n, vector<int>(n, INF));

    if (wait_time >= bee_time[mecho.first][mecho.second]) return false;

    visited[mecho.first][mecho.second] = 0;
    q.push({mecho.first, mecho.second, 0});

    while (!q.empty()) {
        auto [x, y, dist] = q.front(); q.pop();

        int minute = (dist + s - 1) / s;
        if (wait_time + minute >= bee_time[x][y]) continue;

        if (x == home.first && y == home.second) return true;

        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            if (in_bounds(nx, ny) && (grid[nx][ny] == 'G' || grid[nx][ny] == 'D') && visited[nx][ny] > dist + 1) {
                visited[nx][ny] = dist + 1;
                q.push({nx, ny, dist + 1});
            }
        }
    }
    return false;
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> s;
    for (int i = 0; i < n; i++) {
        cin >> grid[i];
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 'M') mecho = {i, j};
            if (grid[i][j] == 'D') home = {i, j};
        }
    }

    bfs_bees();

    int lo = 0, hi = n * n, ans = -1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (can_escape(mid)) {
            ans = mid;
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }

    cout << ans+1 << '\n';
    return 0;
}

• Subtask 1: 21 / 100