제출 #1086286

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1086286		goats_9	Mecho (IOI09_mecho)	C++17	38 / 100	163 ms	7148 KiB

mecho

/* Author: goats_9 */

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

using ll = long long;
constexpr int INF = 1e9;

int main() {
    vector<pair<int, int>> moves = {
        {-1, 0},
        {1, 0},
        {0, 1},
        {0, -1},
    };
    cin.tie(0)->sync_with_stdio(0);
    int n, s;
    cin >> n >> s;
    vector<string> a(n);
    for (auto &u : a) cin >> u;
    vector<vector<int>> bdis(n, vector<int>(n, INF));
    queue<pair<int, int>> q;
    pair<int, int> mecho = {-1, -1}, home = {-1, -1};
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (a[i][j] == 'H') {
                bdis[i][j] = 0;
                q.push({i, j});
            } else if (a[i][j] == 'M') {
                mecho = {i, j};
            } else if (a[i][j] == 'D') {
                home = {i, j};
            }
        }
    }
    while (!q.empty()) {
        auto &[u, v] = q.front();
        q.pop();
        for (auto &[dx, dy] : moves) {
            int uu = u + dx, vv = v + dy;
            if (uu < 0 || uu >= n || vv < 0 || vv >= n || bdis[uu][vv] != INF || (a[uu][vv] != 'G' && a[uu][vv] != 'M')) continue;
            bdis[uu][vv] = bdis[u][v] + 1;
            q.push({uu, vv});
        }
    }
    int l = 0, r = 1e9;
    auto check = [&] (int t) -> bool {
        queue<pair<int, int>> q;
        vector<vector<int>> mdis(n, vector<int> (n, INF));
        mdis[mecho.first][mecho.second] = 0;
        q.push(mecho);
        while (!q.empty()) {
            auto &[u, v] = q.front();
            q.pop();
            if (t + (mdis[u][v] + s - 1) / s > bdis[u][v]) continue;
            if (a[u][v] == 'D') return true;
            for (auto &[dx, dy] : moves) {
                int uu = u + dx, vv = v + dy;
                if (uu < 0 || uu >= n || vv < 0 || vv >= n || mdis[uu][vv] != INF || (a[uu][vv] != 'G' && a[uu][vv] != 'D')) continue;
                mdis[uu][vv] = mdis[u][v] + 1;
                q.push({uu, vv});
            }
        }
        return false;
    };
    while (r - l > 1) {
        int g = (l + r) / 2;
        if (check(g)) l = g;
        else r = g;
    }
    if (check(l)) cout << l;
    else cout << -1;
    return 0;
}

• Subtask 1: 38 / 100