Submission #1232467

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232467		countless	Mecho (IOI09_mecho)	C++20	100 / 100	488 ms	4424 KiB

mecho

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

typedef long long ll;
typedef long double ld;

#define sp <<" "<<
#define endl "\n"

int dr[4] = {0, 0, -1, 1};
int dc[4] = {-1, 1, 0, 0};

void solve() {
    int n, s; cin >> n >> s;
    vector<string> grid(n);
    for (int i = 0; i < n; i++) {
        cin >> grid[i];
    }

    auto check = [&](int cap) -> bool {
        vector<vector<bool>> blocked(n, vector<bool>(n));
        vector<vector<int>> dist(n, vector<int>(n, 1e9));
        using state = tuple<int, int, int>;
        queue<state> p, q;

        state start;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 'H') {
                    q.emplace(i, j, 0);
                    blocked[i][j] = true;
                    dist[i][j] = 0;
                }

                if (grid[i][j] == 'M') {
                    start = make_tuple(i, j, 0);
                }
            }
        }

        auto in = [&](int rr, int cc) -> bool {
            return (0 <= rr and rr < n and 0 <= cc and cc < n);
        };

        while (!q.empty()) {
            auto [r, c, d] = q.front(); q.pop();

            for (int i = 0; i < 4; i++) {
                int nr = r + dr[i], nc = c + dc[i];

                if (in(nr, nc) and !blocked[nr][nc]) {
                    if (grid[nr][nc] == 'M') {
                        blocked[nr][nc] = true;
                        if (d+1 <= cap) {
                            return false;
                        }
                    } else if (grid[nr][nc] == 'G') {
                        if (d+1 > cap) {
                            p.emplace(nr, nc, 1);
                            dist[nr][nc] = 1;
                        } else {
                            q.emplace(nr, nc, d+1);
                            blocked[nr][nc] = true;
                            dist[nr][nc] = 0;
                        }
                    }
                }
            }
        }

        while (!p.empty()) {
            auto [r, c, d] = p.front(); p.pop();

            for (int i = 0; i < 4; i++) {
                int nr = r + dr[i], nc = c + dc[i];

                if (in(nr, nc) and d+1 < dist[nr][nc] and grid[nr][nc] == 'G') {
                    dist[nr][nc] = d+1;
                    p.emplace(nr, nc, d+1);
                }
            }
        }

        q.push(start);
        while (!q.empty()) {
            auto [r, c, d] = q.front(); q.pop();

            if (d > 0 and d % s == 0) {
                queue<int> oth;
            }

            for (int i = 0; i < 4; i++) {
                int nr = r + dr[i], nc = c + dc[i];

                if (in(nr, nc) and !blocked[nr][nc]) {
                    if (grid[nr][nc] == 'D') {
                        return true;
                    } else if (grid[nr][nc] == 'G' and (d+1) / s < dist[nr][nc]) {
                        q.emplace(nr, nc, d+1);
                        blocked[nr][nc] = true;
                    }
                }
            }
        }

        return false;
    };

    int lo = -1, hi = n * n;
    while (hi - lo > 1) {
        int mid = (lo + hi) / 2;

        if (!check(mid)) {
            hi = mid;
        } else {
            lo = mid;
        }
    }

    if (!check(hi)) hi = lo;

    cout << hi << endl;
}

signed main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);

    int t = 1;
    // cin >> t;
    while (t--)
        solve();
}

• Subtask 1: 100 / 100