Submission #1208567

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208567		timeflew	Mecho (IOI09_mecho)	C++20	38 / 100	150 ms	4424 KiB

mecho

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

using pii = pair<int,int>;
static const int MAXN = 800;
static const int INF  = 0x3f3f3f3f;

int n, S;
char grid[MAXN][MAXN];
int vis_bee[MAXN][MAXN];
bool vis_mecho[MAXN][MAXN];
pii st, ed;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

// Can bees spread into (x,y)? They start on 'H' and then only spread into grass 'G' or Mecho's start 'M'.
// They cannot enter trees 'T', home 'D', or hive cells beyond the initial sources.
bool valid_bee(int x, int y) {
    if (x < 0 || x >= n || y < 0 || y >= n) return false;
    char ch = grid[x][y];
    return (ch == 'G' || ch == 'M');
}

// Can Mecho step into (x,y)? He can move on grass 'G', his start 'M', or home 'D', but not on trees 'T' or hives 'H'.
bool valid_mecho(int x, int y) {
    if (x < 0 || x >= n || y < 0 || y >= n) return false;
    char ch = grid[x][y];
    return (ch == 'G' || ch == 'M' || ch == 'D');
}

// After waiting `wait` full minutes at st, can Mecho reach ed before bees catch him?
bool check(int wait) {
    // queue entries: { x, y, minute, steps_used_in_current_minute }
    queue<array<int,4>> q;
    q.push({st.first, st.second, wait, 0});
    memset(vis_mecho, 0, sizeof(vis_mecho));
    vis_mecho[st.first][st.second] = true;

    while (!q.empty()) {
        auto [x, y, minute, used] = q.front();
        q.pop();
        if (x == ed.first && y == ed.second) return true;

        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            if (!valid_mecho(nx, ny)) continue;
            int nused = used + 1;
            int nminute = minute;
            if (nused > S) {
                // move into next minute
                nused = 1;
                nminute++;
            }
            // if bees arrive at or before nminute, it's unsafe
            if (vis_bee[nx][ny] <= nminute) continue;
            if (vis_mecho[nx][ny]) continue;
            vis_mecho[nx][ny] = true;
            q.push({nx, ny, nminute, nused});
        }
    }
    return false;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> S;
    queue<pii> qb;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> grid[i][j];
            if (grid[i][j] == 'H') {
                vis_bee[i][j] = 0;
                qb.push({i, j});
            } else {
                vis_bee[i][j] = INF;
            }
            if (grid[i][j] == 'M') st = {i, j};
            if (grid[i][j] == 'D') ed = {i, j};
        }
    }

    // Multi-source BFS from hives to compute arrival times of bees
    while (!qb.empty()) {
        auto [x, y] = qb.front(); qb.pop();
        int t = vis_bee[x][y];
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            if (!valid_bee(nx, ny)) continue;
            if (vis_bee[nx][ny] > t + 1) {
                vis_bee[nx][ny] = t + 1;
                qb.push({nx, ny});
            }
        }
    }

    // Binary search the maximum waiting time
    int lo = 0, hi = n * n, ans = -1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (check(mid)) {
            ans = mid;
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }

    cout << ans << "\n";
    return 0;
}

• Subtask 1: 38 / 100