Submission #1243731

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243731		marcus06	Mecho (IOI09_mecho)	C++20	97 / 100	189 ms	6180 KiB

mecho

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

/*How to use:
    Tvector <int, 2> g(n); //graph
    Tvector <int, 3> f(n, k, 2) = f[n][k][2]
*/
template <class Tp, int D = 1>
struct Tvector : public vector<Tvector<Tp, D - 1>> {
    template <class... Args>
    Tvector(int n = 0, Args... args) : vector<Tvector<Tp, D - 1>>(n, Tvector<Tp, D - 1>(args...)) {}
};

template <class Tp>
struct Tvector<Tp, 1> : public vector<Tp> {
    Tvector(int n = 0, Tp val = Tp()) : vector<Tp>(n, val) {}
};

#ifdef LOCAL
#include </home/marcus06/CP/Library/debug.h>
#else
#define debug(...) 
#endif

const int dx[] = {0, 0, -1, 1};
const int dy[] = {-1, 1, 0, 0};
 
void solve() {
    int n, s;
    cin >> n >> s;

    Tvector <char, 2> g(n, n);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> g[i][j];
        }
    }

    int h_x, h_y;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (g[i][j] == 'D') {
                h_x = i;
                h_y = j;
            }
        }
    }

    int m_x, m_y;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (g[i][j] == 'M') {
                m_x = i;
                m_y = j;
            }
        }
    }

    auto valid = [&](int x, int y) -> bool {
        return (x >= 0 && y >= 0 && x < n && y < n && (g[x][y] == 'G' || g[x][y] == 'M'));
    };

    Tvector <int, 2> bee_dist(n, n, -1);
    {
        queue <pair <int, int>> q;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (g[i][j] == 'H') {
                    bee_dist[i][j] = 0;
                    q.emplace(i, j);
                }
            }
        }
        while (!q.empty()) {
            auto [x, y] = q.front(); q.pop();
            for (int i = 0; i < 4; ++i) {
                int u = x + dx[i], v = y + dy[i];
                if (u == h_x && v == h_y) continue;
                if (valid(u, v) && bee_dist[u][v] == -1) {
                    bee_dist[u][v] = bee_dist[x][y] + 1;
                    q.emplace(u, v);
                }
            }
        }
    }

    Tvector <int, 2> Mecho_dist(n, n);
    auto possible = [&](int t) -> bool {
        queue <pair <int, int>> q;
        fill(Mecho_dist.begin(), Mecho_dist.end(), Tvector <int, 1> (n, -1));

        q.emplace(m_x, m_y);
        Mecho_dist[m_x][m_y] = 0;
        if (bee_dist[m_x][m_y] <= t) q.pop();
        while (!q.empty()) {
            auto [x, y] = q.front(); q.pop();
            for (int i = 0; i < 4; ++i) {
                int u = x + dx[i], v = y + dy[i];
                if (valid(u, v) && Mecho_dist[u][v] == -1) {
                    int nxt_dist = t + Mecho_dist[x][y] / s;
                    if (nxt_dist < bee_dist[u][v]) {
                        Mecho_dist[u][v] = Mecho_dist[x][y] + 1;
                        q.emplace(u, v);
                    }
                }
            }
        }

        bool is_success = false;
        for (int i = 0; i < 4; ++i) {
            int u = h_x + dx[i], v = h_y + dy[i];
            if (valid(u, v) && Mecho_dist[u][v] != -1) {
                if (t + Mecho_dist[u][v] / s < bee_dist[u][v]) is_success = true;
            }
        }
        return is_success;
    };

    int l = -1, r = int(1e9);
    while (r - l > 1) {
        int mid = (l + r) / 2;
        if (possible(mid))
            l = mid;
        else
            r = mid;
    }
    if (!possible(0)) l = -1;
    cout << l << '\n';
}

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
#ifdef LOCAL
    auto begin = std::chrono::high_resolution_clock::now();
#endif

    int tt = 1;
    while (tt--) {
        solve();
    }

#ifdef LOCAL
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    std::cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
#endif
    return 0;
}

• Subtask 1: 97 / 100