Submission #1230263

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230263		lukasuliashvili	Mecho (IOI09_mecho)	C++20	48 / 100	125 ms	6236 KiB

mecho

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

const int N = 805;
int n, s;
char grid[N][N];
int bee_time[N][N], mecho_time[N][N];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
pair<int, int> start, home;
vector<pair<int, int>> hives;

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

void bfs_bees() {
    queue<pair<int, int>> q;
    for (auto [x, y] : hives) {
        bee_time[x][y] = 0;
        q.push({x, y});
    }

    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)) continue;
            if (grid[nx][ny] == 'T' || grid[nx][ny] == 'D') continue; // Bees can't enter trees or home
            if (bee_time[nx][ny] > bee_time[x][y] + s) {
                bee_time[nx][ny] = bee_time[x][y] + s;
                q.push({nx, ny});
            }
        }
    }
}

bool can_escape(int wait_time) {
    for (int i = 0; i < n; i++)
        fill(mecho_time[i], mecho_time[i] + n, INT_MAX);

    queue<pair<int, int>> q;
    mecho_time[start.first][start.second] = wait_time;
    q.push(start);

    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)) continue;
            if (grid[nx][ny] == 'T') continue;

            int arrive = mecho_time[x][y] + 1;
            if (arrive >= bee_time[nx][ny]) continue; // bees arrive before or same second

            if (mecho_time[nx][ny] > arrive) {
                mecho_time[nx][ny] = arrive;
                if (grid[nx][ny] == 'D') return true;
                q.push({nx, ny});
            }
        }
    }

    return false;
}

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

    cin >> n >> s;
    for (int i = 0; i < n; i++)
        cin >> grid[i];

    for (int i = 0; i < n; i++)
        fill(bee_time[i], bee_time[i] + n, INT_MAX);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 'M') start = {i, j};
            if (grid[i][j] == 'D') home = {i, j};
            if (grid[i][j] == 'H') hives.emplace_back(i, j);
        }
    }

    bfs_bees();

    int l = 0, r = (n * n + s - 1) / s + 10; // upper bound on minutes
    int ans = -1;
    while (l <= r) {
        int mid = (l + r) / 2;
        int wait_time = mid * s; // convert minutes to seconds
        if (can_escape(wait_time)) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }

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

• Subtask 1: 48 / 100