Submission #996978

#	Time	Username	Problem	Language	Result	Execution time	Memory
996978		imann	Mecho (IOI09_mecho)	C++17	39 / 100	162 ms	6492 KiB

mecho

#include <iostream>
#include <array>
#include <string>
#include <queue>

const int MAX_N = 800 + 1;
const int INF = 1e9;

std::array<std::string, MAX_N> grid;
std::array<std::array<int, MAX_N>, MAX_N> minuteToBeHive, level;

void bfs(int n) {
    std::queue<std::pair<int, int>> q;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            minuteToBeHive[i][j] = INF;
            if (grid[i][j] == 'H') {
                q.push({i, j});
                minuteToBeHive[i][j] = 0;
            }
        }
    }

    while (!q.empty()) {
        auto v = q.front();
        q.pop();
        if (v.first > 0) {
            if (grid[v.first - 1][v.second] == 'G') {
                if (minuteToBeHive[v.first - 1][v.second] == INF)
                    q.push({v.first - 1, v.second});
                minuteToBeHive[v.first - 1][v.second] = std::min(minuteToBeHive[v.first - 1][v.second], minuteToBeHive[v.first][v.second] + 1);
            }
        }
        if (v.first < n - 1) {
            if (grid[v.first + 1][v.second] == 'G') {
                if (minuteToBeHive[v.first + 1][v.second] == INF)
                    q.push({v.first + 1, v.second});
                minuteToBeHive[v.first + 1][v.second] = std::min(minuteToBeHive[v.first + 1][v.second], minuteToBeHive[v.first][v.second] + 1);
            }
        }
        if (v.second > 0) {
            if (grid[v.first][v.second - 1] == 'G') {
                if (minuteToBeHive[v.first][v.second - 1] == INF)
                    q.push({v.first, v.second - 1});
                minuteToBeHive[v.first][v.second - 1] = std::min(minuteToBeHive[v.first][v.second - 1], minuteToBeHive[v.first][v.second] + 1);
            }
        }
        if (v.second < n - 1) {
            if (grid[v.first][v.second + 1] == 'G') {
                if (minuteToBeHive[v.first][v.second + 1] == INF)
                    q.push({v.first, v.second + 1});
                minuteToBeHive[v.first][v.second + 1] = std::min(minuteToBeHive[v.first][v.second + 1], minuteToBeHive[v.first][v.second] + 1);
            }
        }
    }
}

bool bfs2(int n, int s, int startMinute) {
    std::pair<int, int> start, end;
    std::queue<std::pair<int, int>> q;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            level[i][j] = INF;
            if (grid[i][j] == 'M')
                start = {i, j};
            if (grid[i][j] == 'D')
                end = {i, j};
        }
    }
    q.push(start);
    level[start.first][start.second] = 0;
    while (!q.empty()) {
        auto v = q.front();
        q.pop();
        if (v.first > 0) {
            if ((grid[v.first - 1][v.second] == 'G' || grid[v.first - 1][v.second] == 'D') && (startMinute + (level[v.first][v.second] + 1) / s < minuteToBeHive[v.first - 1][v.second])) {
                if (level[v.first - 1][v.second] == INF)
                    q.push({v.first - 1, v.second});
                level[v.first - 1][v.second] = std::min(level[v.first - 1][v.second], level[v.first][v.second] + 1);
            }
        }
        if (v.first < n - 1) {
            if ((grid[v.first + 1][v.second] == 'G' || grid[v.first + 1][v.second] == 'D') && (startMinute + (level[v.first][v.second] + 1) / s < minuteToBeHive[v.first + 1][v.second])) {
                if (level[v.first + 1][v.second] == INF)
                    q.push({v.first + 1, v.second});
                level[v.first + 1][v.second] = std::min(level[v.first + 1][v.second], level[v.first][v.second] + 1);
            }
        }
        if (v.second > 0) {
            if ((grid[v.first][v.second - 1] == 'G' || grid[v.first][v.second - 1] == 'D') && (startMinute + (level[v.first][v.second] + 1) / s < minuteToBeHive[v.first][v.second - 1])) {
                if (level[v.first][v.second - 1] == INF)
                    q.push({v.first, v.second - 1});
                level[v.first][v.second - 1] = std::min(level[v.first][v.second - 1], level[v.first][v.second] + 1);
            }
        }
        if (v.second < n - 1) {
            if ((grid[v.first][v.second + 1] == 'G' || grid[v.first][v.second + 1] == 'D') && (startMinute + (level[v.first][v.second] + 1) / s < minuteToBeHive[v.first][v.second + 1])) {
                if (level[v.first][v.second + 1] == INF)
                    q.push({v.first, v.second + 1});
                level[v.first][v.second + 1] = std::min(level[v.first][v.second + 1], level[v.first][v.second] + 1);
            }
        }
    }
    return level[end.first][end.second] != INF;
}

int solve(int n, int s) {
    bfs(n);
    int l = 0, r = n;
    while (r - l > 1) {
        int mid = (r + l) / 2;
        if (bfs2(n, s, mid)) {
            l = mid;
        } else {
            r = mid;
        }
    }

    if (bfs2(n, s, l))
        return l;
    return -1;
}

int main() {
    int n, s; std::cin >> n >> s;
    for (int i = 0; i < n; ++i) {
        std::cin >> grid[i];
    }
    std::cout << solve(n, s) << std::endl;
}

• Subtask 1: 39 / 100