Submission #1239315

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239315		chr34	Mecho (IOI09_mecho)	C++20	100 / 100	442 ms	11944 KiB

mecho

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

#define int long long
#define endl "\n"
const int INF = 1e18;
const int MAXN = 810;
const int MOD = 1e9 + 7;

int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

int n, s;
vector<string> a;
vector<pair<int, int>> hives;
int mex, mey;
int homex, homey;

vector<vector<int>> btime, mtime;

bool ok(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < n && (a[x][y] == 'G' || a[x][y] == 'M');
}

bool can_reach(int mdis, int bdis) {
    return mdis / s < bdis;
}

void bbfs() {
    vector<vector<bool>> bees_vis(n, vector<bool>(n, false));
    btime.assign(n, vector<int>(n, INF));

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

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

bool mbfs(int t) {
    vector<vector<bool>> mvis(n, vector<bool>(n, false));
    mtime.assign(n, vector<int>(n, INF));

    queue<pair<int, int>> q;
    if (btime[mex][mey] - t > 0) {
        q.push({mex, mey});
        mvis[mex][mey] = true;
        mtime[mex][mey] = 0;
    }

    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();

        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i], ny = y + dy[i];
            if (!ok(nx, ny) || mvis[nx][ny]) continue;
            int new_mtime = mtime[x][y] + 1;
            if (can_reach(new_mtime, btime[nx][ny] - t)) {
                mvis[nx][ny] = true;
                mtime[nx][ny] = new_mtime;
                q.push({nx, ny});
            }
        }
    }

    for (int i = 0; i < 4; ++i) {
        int nx = homex + dx[i], ny = homey + dy[i];
        if (nx >= 0 && nx < n && ny >= 0 && ny < n && mvis[nx][ny] && can_reach(mtime[nx][ny], btime[nx][ny] - t)) {
            return true;
        }
    }
    return false;
}

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

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

    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j) {
            if (a[i][j] == 'M') mex = i, mey = j;
            if (a[i][j] == 'H') hives.emplace_back(i, j);
            if (a[i][j] == 'D') homex = i, homey = j;
        }

    int l = 0, r = n * n, ans = -1;
    while (l <= r) {
        int mid = (l + r) / 2;
        bbfs();
        if (mbfs(mid)) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }

    cout << ans << endl;
    return 0;
}

• Subtask 1: 100 / 100