← Real problems

ioi09p6

hardbfsgridbinary-searchStatement on DMOJ

CP Lang

14 lines0.3 spec
// ioi09p6 Mecho: the longest wait at the honey after which the bear still gets home. Bees spread
// one cell a minute from every hive (BFS); the bear makes up to s steps a minute, so after a wait
// of w he may enter a cell at step k only while w + k / s is before the bees arrive. Waiting
// longer never helps, so the answer is the last w that escapes.
let (n, s) = read<(1..=800, 1..=1_000)>()
let g = read<[n, n]Char>()
let cell = ch => g.keys.find(p => g[p] == ch)!
let (honey, home) = (cell('M'), cell('D'))
let bees = bfs(p => p.adj4.filter(q => g[q] in "GM"), from: g.keys.filter(p => g[p] == 'H'))
fn escapes(w: Int) -> Bool:
    let safe = (p, k) => (bees.dist[p] ?? inf) > w + k / s
    let walk = bfs(p => p.adj4.filter(q => g[q] in "GD"), from: [honey], until: home, enter: safe)
    safe(honey, 0) and walk.dist[home] != None
print((0..n * n).last_true(escapes) ?? -1)

Accepted C++

137 lines · 3.02 s on the judge
#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
    cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t << " | ";
    dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
         << ": ";                                          \
    dbgh(__VA_ARGS__)
#else
#define cerr   \
    if (false) \
    cerr
#define dbg(...)
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

#define int long

constexpr int maxn = 1005, dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

void solve() {
    int n, kv;
    cin >> n >> kv;
    string arr[n];
    for (auto& a : arr) {
        cin >> a;
    }
    int sx, sy, tx, ty;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (arr[i][j] == 'M') {
                arr[i][j] = 'G';
                sx = i;
                sy = j;
            } else if (arr[i][j] == 'D') {
                tx = i;
                ty = j;
            }
        }
    }
    auto ibs = [&](int x, int y) -> bool {
        return 0 <= x && x < n && 0 <= y && y < n;
    };
    int dist[maxn][maxn];
    memset(dist, 0x3f, sizeof(dist));
    {
        queue<pair<int, int>> q;
        auto push = [&](int x, int y, int d) -> void {
            if (d < dist[x][y]) {
                dist[x][y] = d;
                q.emplace(x, y);
            }
        };
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (arr[i][j] == 'H') {
                    push(i, j, 0);
                }
            }
        }
        while (sz(q)) {
            auto [x, y] = q.front();
            q.pop();
            for (auto& [dx, dy] : dirs) {
                int cx = x + dx, cy = y + dy;
                if (ibs(cx, cy) && arr[cx][cy] == 'G') {
                    push(cx, cy, dist[x][y] + 1);
                }
            }
        }
    }
    auto check = [&](int t) -> bool {
        if (dist[sx][sy] <= t) {
            return false;
        }
        bool vis[maxn][maxn] {};
        queue<array<int, 3>> q;
        auto push = [&](int x, int y, int d) -> void {
            if (!vis[x][y]) {
                vis[x][y] = true;
                q.push({x, y, d});
            }
        };
        push(sx, sy, kv * t);
        while (sz(q)) {
            auto [x, y, d] = q.front();
            if (x == tx && y == ty) {
                return true;
            }
            q.pop();
            for (auto& [dx, dy] : dirs) {
                int cx = x + dx, cy = y + dy;
                if (ibs(cx, cy) && (arr[cx][cy] == 'G' || arr[cx][cy] == 'D') &&
                    dist[cx][cy] > (d + 1) / kv) {
                    push(cx, cy, d + 1);
                }
            }
        }
        return false;
    };
    if (!check(0)) {
        cout << -1 << endl;
        return;
    }
    int l = 0, r = 1e9;
    while (l < r) {
        int mid = (l + r + 1) / 2;
        if (check(mid)) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }
    cout << l << endl;
}

int32_t main() {
    cin.tie(nullptr);
    cin.exceptions(ios::failbit);
    ios_base::sync_with_stdio(false);
    solve();
}