Submission #648700

#	Time	Username	Problem	Language	Result	Execution time	Memory
648700		borisAngelov	Mecho (IOI09_mecho)	C++17	100 / 100	534 ms	8280 KiB

mecho

#include <iostream>
#include <utility>
#include <vector>
#include <queue>
#include <tuple>

using namespace std;

const int MAXN = 805;

int n, s;
char table[MAXN][MAXN];

vector<pair<int, int>> hives;
int home_x, home_y;
int mecho_x, mecho_y;

bool visited_b[MAXN][MAXN];
bool visited_m[MAXN][MAXN];
int levels_b[MAXN][MAXN];
int levels_m[MAXN][MAXN];

pair<int, int> dirs[4] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};

bool isValid(int x, int y) {
    return x >= 1 && x <= n && y >= 1 && y <= n && (table[x][y] == 'G' || table[x][y] == 'M');
}

bool canReachIt(int mecho_time, int bees_time) {
    return mecho_time / s < bees_time;
}

bool check(int eating_time) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            visited_b[i][j] = visited_m[i][j] = false;
            levels_b[i][j] = levels_m[i][j] = 0;
        }
    }

    queue<pair<int, int>> q;

    for (auto hive : hives) {
        q.push(hive);
        visited_b[hive.first][hive.second] = true;
    }

    while (!q.empty()) {
        int x, y; tie(x, y) = q.front();
        q.pop();

        for (int d = 0; d < 4; d++) {
            int x2 = x + dirs[d].first;
            int y2 = y + dirs[d].second;

            if (!isValid(x2, y2)) continue;
            if (visited_b[x2][y2] == true) continue;

            q.push({x2, y2});
            visited_b[x2][y2] = true;
            levels_b[x2][y2] = 1 + levels_b[x][y];
        }
    }

    q.push({mecho_x, mecho_y});
    visited_m[mecho_x][mecho_y] = true;

    if (levels_b[mecho_x][mecho_y] <= eating_time) {
        return false;
    }

    while (!q.empty()) {
        int x, y; tie(x, y) = q.front();
        q.pop();

        for (int d = 0; d < 4; d++) {
            int x2 = x + dirs[d].first;
            int y2 = y + dirs[d].second;

            if (!isValid(x2, y2)) continue;
            if (visited_m[x2][y2] == true) continue;
            if (!canReachIt(levels_m[x][y] + 1, levels_b[x2][y2] - eating_time)) continue;

            q.push({x2, y2});
            visited_m[x2][y2] = true;
            levels_m[x2][y2] = 1 + levels_m[x][y];
        }
    }

    bool isReached = false;

    for (int d = 0; d < 4; d++) {
        int x = home_x + dirs[d].first;
        int y = home_y + dirs[d].second;

        if (isValid(x, y) && visited_m[x][y] && canReachIt(levels_m[x][y], levels_b[x][y] - eating_time)) {
            isReached = true;
            break;
        }
    }

    return isReached;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> s;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> table[i][j];

            if (table[i][j] == 'H') hives.push_back({i, j});

            if (table[i][j] == 'M') {
                mecho_x = i;
                mecho_y = j;
            }

            if (table[i][j] == 'D') {
                home_x = i;
                home_y = j;
            }
        }
    }

    int l = 0;
    int r = n * n;

    while (l <= r) {
        int mid = (l + r) / 2;

        if (check(mid)) l = mid + 1;
        else r = mid - 1;
    }

    cout << r << endl;

    return 0;
}

• Subtask 1: 100 / 100