Submission #1266824

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266824		khfares	Mecho (IOI09_mecho)	C++20	71 / 100	428 ms	11376 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll  = long long;
using pll = pair<ll, ll>;
ll x, y;
vector<ll> mx = {1, -1, 0, 0}, my = {0, 0, 1, -1};
bool good(ll n, ll s, vector<string>& board, vector<vector<ll>>& disfh, ll m) {
    vector<vector<ll>> dis(n, vector<ll> (n, -1));
    dis[x][y] = m;
    queue<vector<ll>> q;
    q.push({x, y});
    while (!q.empty()) {
        auto v = q.front();
        q.pop();
        if (board[v[0]][v[1]] == 'D') {
            return true;
        }
        for (ll i = 0; i < 4; i++) {
            ll nx = v[0] + mx[i], ny = v[1] + my[i];
            if (nx >= n || nx < 0 || ny >= n || ny < 0) continue;
            if (dis[nx][ny] != -1) continue;
            if (board[nx][ny] == 'T') continue;
            if (((dis[v[0]][v[1]] + 1-m)/s)+m >= disfh[nx][ny]) continue;
            dis[nx][ny] = dis[v[0]][v[1]] + 1;
            q.push({nx, ny});
        }
    }
    return false;
}
int main() {
    //ios_base::sync_with_stdio(false);
    //cin.tie(nullptr);
    //___________________________
    ll n, s; cin >> n >> s;
    vector<string> board(n);
    for (ll i = 0; i < n; i++) cin >> board[i];
    //___________________________
    vector<vector<ll>> disfh(n, vector<ll>(n, -1));
    queue<vector<ll>> q;
    ll dx = 0, dy = 0;
    for (ll i = 0; i < n; i++) {
        for (ll j = 0; j < n; j++) {
            if (board[i][j] == 'H') q.push({i, j}), disfh[i][j] = 0;
            if (board[i][j] == 'M') x = i, y = j;
            if (board[i][j] == 'D') dx = i, dy = j;
        }
    }
    disfh[dx][dy] = 1e18;
    while (!q.empty()) {
        auto v = q.front();
        q.pop();
        for (ll i = 0; i < 4; i++) {
            ll nx = v[0]+mx[i], ny = v[1]+my[i];
            if (nx >= n || nx < 0 || ny >= n || ny < 0) continue;
            if (disfh[nx][ny] != -1) continue;
            if (board[nx][ny] == 'T' || board[nx][ny] == 'D') continue;
            disfh[nx][ny] = disfh[v[0]][v[1]]+1;
            q.push({nx, ny});
        }
    }
    for (ll i = 0; i < 4; i++) {
        ll nx = dx+mx[i], ny = dy+my[i];
        if (nx >= n || nx < 0 || ny >= n || ny < 0) continue;
        if (board[nx][ny] == 'T') continue;
        disfh[dx][dy] = min(disfh[dx][dy], disfh[nx][ny]+1);
    }
    ll ans = 1e18;
    if (!good(n, s, board, disfh, 0)) {
        cout << -1 << endl;
        return 0;
    }
    ll l = 0, r = 1e18;
    while (l <= r) {
        ll m = (l+r)/2;
        if (good(n, s, board, disfh, m)) {
            l = m+1;
            ans = m;
        }
        else r = m-1;
    }
    cout << ans << endl;

    return 0;
}

• Subtask 1: 71 / 100