Submission #1175725

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175725		jirayu	Mecho (IOI09_mecho)	C++20	4 / 100	18 ms	6216 KiB

mecho

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

const int INF = 1e9;

int N, S;
vector<string> grid;
int bee_time[800][800];
int mecho_time[800][800];
pair<int, int> mecho_pos, home_pos;
vector<pair<int, int>> hives;

int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

bool isValid(int x, int y) {
    return x >= 0 && x < N && y >= 0 && y < N && grid[x][y] != 'T';
}

void bfsBees() {
    queue<pair<int, int>> q;
    for (auto& hive : hives) {
        q.push(hive);
        bee_time[hive.first][hive.second] = 0;
    }

    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        for (auto& d : directions) {
            int nx = x + d[0], ny = y + d[1];
            if (isValid(nx, ny) && grid[nx][ny] == 'G' && bee_time[nx][ny] == INF) {
                bee_time[nx][ny] = bee_time[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }
}

void bfsMecho(int maxTime) {
    queue<pair<int, int>> q;
    memset(mecho_time, INF, sizeof(mecho_time));
    q.push(mecho_pos);
    mecho_time[mecho_pos.first][mecho_pos.second] = 0;

    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        int currentTime = mecho_time[x][y];
        if (currentTime >= maxTime) break;

        for (auto& d : directions) {
            for (int steps = 1; steps <= S; ++steps) {
                int nx = x + d[0] * steps, ny = y + d[1] * steps;
                if (isValid(nx, ny) && grid[nx][ny] == 'G' && mecho_time[nx][ny] == INF) {
                    if (mecho_time[nx][ny] > currentTime + 1) {
                        mecho_time[nx][ny] = currentTime + 1;
                        q.push({nx, ny});
                    }
                }
            }
        }
    }
}

bool canEscape(int minutes) {
    bfsMecho(minutes);
    return mecho_time[home_pos.first][home_pos.second] <= minutes && mecho_time[home_pos.first][home_pos.second] < bee_time[home_pos.first][home_pos.second];
}

int main() {
    cin >> N >> S;
    grid.resize(N);
    for (int i = 0; i < N; ++i) {
        cin >> grid[i];
    }

    // Locate positions
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (grid[i][j] == 'M') mecho_pos = {i, j};
            if (grid[i][j] == 'D') home_pos = {i, j};
            if (grid[i][j] == 'H') hives.push_back({i, j});
        }
    }

    // Initialize bee_time with INF
    memset(bee_time, INF, sizeof(bee_time));
    bfsBees();

    // Binary search to find the largest number of minutes
    int left = 0, right = N * N, answer = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (canEscape(mid)) {
            answer = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    cout << answer << endl;
    return 0;
}

• Subtask 1: 4 / 100