Submission #965431

#	Time	Username	Problem	Language	Result	Execution time	Memory
965431		Alihan_8	Mecho (IOI09_mecho)	C++17	59 / 100	640 ms	16736 KiB

mecho

#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
#define int long long

using i64 = long long;

template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}

const int inf = 1e9;

int dx[] = {0, -1, 0, 1};
int dy[] = {1, 0, -1, 0};

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

    int n, k; cin >> n >> k;
    vector <string> a(n);
    for ( auto &u: a ) cin >> u;
    ar <int,2> s, e;
    vector <vector<int>> bee(n, vector <int> (n, inf));
    queue <ar<int,2>> q;
    for ( int i = 0; i < n; i++ ){
        for ( int j = 0; j < n; j++ ){
            if ( a[i][j] == 'M' ){
                s = {i, j};
            }
            if ( a[i][j] == 'D' ){
                e = {i, j};
            }
            if ( a[i][j] == 'H' ){
                q.push({i, j});
                bee[i][j] = 0;
            }
        }
    }
    auto ok = [&](int u, int v){
        return u >= 0 && v >= 0 && u < n && v < n;
    };
    while ( !q.empty() ){
        auto [u, v] = q.front();
        q.pop();
        for ( int i = 0; i < 4; i++ ){
            int x = dx[i] + u, y = dy[i] + v;
            if ( ok(x, y) && a[x][y] != 'T' && a[x][y] != 'D' ){
                if ( chmin(bee[x][y], bee[u][v] + 1) ){
                    q.push({x, y});
                }
            }
        }
    }
    auto valid = [&](int t){
        if ( bee[s[0]][s[1]] <= t ){
            return false;
        }
        vector <vector<ar<int,2>>> dp(n, vector <ar<int,2>> (n, {inf, inf}));
        dp[s[0]][s[1]] = {t + 1, -k};
        priority_queue <ar<int,4>> q;
        q.push({-(t + 1), k, s[0], s[1]});
        while ( !q.empty() ){
            auto [val, r, u, v] = q.top();
            q.pop(); val *= -1;
            if ( dp[u][v] != ar<int,2>{val, -r} ){
                continue;
            }
            for ( int i = 0; i < 4; i++ ){
                int x = dx[i] + u, y = dy[i] + v;
                if ( !ok(x, y) || a[x][y] == 'T' ){
                    continue;
                }
                if ( r == 0 ){
                    if ( chmin(dp[x][y], ar<int,2>{val + 1, -k}) ){
                        q.push({-dp[x][y][0], k, x, y});
                    }
                } else{
                    if ( bee[x][y] > val - (r != 1) ){
                        if ( chmin(dp[x][y], ar<int,2>{val, -(r - 1)}) ){
                            q.push({-dp[x][y][0], r - 1, x, y});
                        }
                    }
                }
            }
        }
        return dp[e[0]][e[1]][0] != inf;
    };
    int l = 0, r = inf;
    while ( l + 1 < r ){
        int md = (l + r) >> 1;
        if ( valid(md) ){
            l = md;
        } else r = md;
    }
    cout << (valid(l) ? l : -1);

    cout << '\n';
}

• Subtask 1: 59 / 100