제출 #1175742

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1175742		PakinDioxide	Mecho (IOI09_mecho)	C++17	100 / 100	549 ms	16720 KiB

mecho

/*
    author  : PakinDioxide
    created : 29/03/2025 13:16
    task    : IOI09_mecho
*/
#include <bits/stdc++.h>
#define ll long long

using namespace std;

pair <int, int> d[4] = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    ll n, s;
    cin >> n >> s;
    string a[n];
    int sx = 0, sy = 0, ex = 0, ey = 0;
    for (int i = 0; i < n; i++) cin >> a[i];
    priority_queue <tuple <ll, int, int>> q;
    ll dis[n][n];
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) dis[i][j] = LLONG_MAX;
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
        if (a[i][j] == 'M') sx = i, sy = j;
        else if (a[i][j] == 'D') ex = i, ey = j;
        else if (a[i][j] == 'H') q.emplace(0, i, j), dis[i][j] = 0;
    }
    while (!q.empty()) {
        auto [w, x, y] = q.top();
        q.pop();
        w=-w;
        if (w != dis[x][y]) continue;
        for (auto [dx, dy] : d) {
            int nx = x+dx, ny = y+dy;
            if (nx < 0 || nx >= n || ny < 0 || ny >= n || a[nx][ny] == 'T' || a[nx][ny] == 'D') continue;
            if (dis[nx][ny] > w+1) q.emplace(-(dis[nx][ny] = w+1), nx, ny);
        }
    }
    // for (int i = 0; i < n; i++) {
    //     for (int j = 0; j < n; j++) cout << (dis[i][j] == LLONG_MAX ? -1 : dis[i][j]) << ' ';
    //     cout << '\n';
    // }
    priority_queue <tuple <pair <ll, ll>, int, int>> Q;
    ll l = 0, r = n*n, ans = -1;
    while (l <= r) {
        ll k = l + (r-l)/2, ok = 0;
        Q.emplace(make_pair(-k, 0LL), sx, sy);
        pair <ll, ll> dis2[n][n];
        for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) dis2[i][j] = {LLONG_MAX, LLONG_MAX};
        dis2[sx][sy] = {k, 0};
        while (!Q.empty()) {
            auto [w, x, y] = Q.top();
            Q.pop();
            w.first = -w.first;
            w.second = -w.second;
            if (dis2[x][y] != w) continue;
            if (dis[x][y] <= w.first) continue;
            // cout << k << ' ' << dis[x][y] << ' ' << w << ' ' << x << ' ' << y << '\n';
            if (x == ex && y == ey) {
                ok = 1;
                break;
            }
            pair <ll, ll> nw = {w.first + (w.second + 1 == s), (w.second + 1) % s};
            pair <ll, ll> nnw = {-nw.first, -nw.second};
            for (auto [dx, dy] : d) {
                int nx = x+dx, ny = y+dy;
                if (nx < 0 || nx >= n || ny < 0 || ny >= n || a[nx][ny] == 'T') continue;
                if (dis2[nx][ny] > nw) {
                    dis2[nx][ny] = nw;
                    Q.emplace(nnw, nx, ny);
                }
            }
        }
        while (!q.empty()) q.pop();
        if (ok) l = k+1, ans = k;
        else r = k-1;
    }
    cout << ans << '\n';
}

• Subtask 1: 100 / 100