Submission #1208560

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208560		timeflew	Mecho (IOI09_mecho)	C++20	13 / 100	143 ms	4572 KiB

mecho

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

#define ll long long
#define ff first
#define ss second

const int mxN = 8e2;

char c[mxN][mxN];
int vis[mxN][mxN];   // Time bees reach each cell
bool vis1[mxN][mxN]; // Visited in Mecho's BFS
pair<int, int> st, ed;
int n, s;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

// Bees spread to grassy cells only (G, M)
bool bee_valid(int x, int y) {
    return (x >= 0 && x < n && y >= 0 && y < n && (c[x][y] == 'G' || c[x][y] == 'M'));
}

// Mecho moves to grass (G, M) and home (D)
bool mecho_valid(int x, int y) {
    return (x >= 0 && x < n && y >= 0 && y < n && 
            (c[x][y] == 'G' || c[x][y] == 'M' || c[x][y] == 'D'));
}

bool check(int x) {
    // Check if Mecho is safe at M for x minutes
    if (vis[st.ff][st.ss] <= x) return 0;

    queue<array<int, 4>> q; // {x, y, step, state}
    q.push({st.ff, st.ss, x + 1, 0});
    memset(vis1, 0, sizeof(vis1));
    vis1[st.ff][st.ss] = 1;

    while (!q.empty()) {
        auto [xx, yy, step, state] = q.front();
        q.pop();
        if (xx == ed.ff && yy == ed.ss) return 1;

        for (int i = 0; i < 4; i++) {
            int nx = xx + dx[i], ny = yy + dy[i];
            if (mecho_valid(nx, ny) && vis[nx][ny] > step && !vis1[nx][ny]) {
                vis1[nx][ny] = 1;
                int new_state = state + 1;
                if (new_state == s) {
                    q.push({nx, ny, step + 1, 0});
                } else {
                    q.push({nx, ny, step, new_state});
                }
            }
        }
    }
    return 0;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> s;

    // Compute bee spread times
    queue<array<int, 3>> q;
    memset(vis, 0x3f, sizeof(vis));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> c[i][j];
            if (c[i][j] == 'M') st = {i, j};
            if (c[i][j] == 'D') ed = {i, j};
            if (c[i][j] == 'H') q.push({i, j, 0}), vis[i][j] = 0;
        }
    }

    while (!q.empty()) {
        auto [x, y, now] = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (vis[nx][ny] == 0x3f3f3f3f && bee_valid(nx, ny)) {
                vis[nx][ny] = now + 1;
                q.push({nx, ny, now + 1});
            }
        }
    }

    // Binary search for maximum k
    int l = 0, r = n, ans = -1; // r=n is safer than r=s
    while (l <= r) {
        int mid = (l + r) / 2;
        if (check(mid)) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    cout << ans << "\n";
    return 0;
}

• Subtask 1: 13 / 100