제출 #1248258

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1248258		nastya_an	Mecho (IOI09_mecho)	C++20	39 / 100	96 ms	6232 KiB

mecho

//#pragma GCC optimize("Ofast,unroll-loops,fast-math")
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define cin(v) \
    for (auto &el : v) { cin >> el; }
#define cout(v)                               \
    for (auto &el : v) { cout << el << " "; } \
    cout << "\n";

using namespace std;
using ll = long long;
using db = double;
using ldb = long double;
const ldb EPS = 1e-9;
const ll LINF = 2e18;
const ll MOD = 1e9 + 7;
const ll MOD2 = 1072005019;
const ll MOD3 = 998244353;
const ldb PI = acos(-1.0);

vector<string> mas;

bool good(int x, int y) {
    if (x >= 0 && x < mas.size() && y >= 0 && y < mas.size() && mas[x][y] != 'T') {
        return true;
    }
    return false;
}

void solve() {
    int n, d;
    cin >> n >> d;
    mas.resize(n);
    cin(mas);
    vector<vector<int>> dist(n, vector<int>(n, 2e9));
    queue<pair<int, int>> q;
    int X = 0, Y = 0;
    int X_home = 0, Y_home = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (mas[i][j] == 'H') {
                q.push({i, j});
                dist[i][j] = 0;
            }
            if (mas[i][j] == 'M') {
                X = i;
                Y = j;
            }
            if (mas[i][j] == 'D') {
                X_home = i;
                Y_home = j;
            }
        }
    }
    while (q.size()) {
        pair<int, int> p = q.front();
        q.pop();
        int x = p.first, y = p.second;
        if (x >= 1) {
            if (dist[x - 1][y] > dist[x][y] + 1) {
                dist[x - 1][y] = dist[x][y] + 1;
                q.push({x - 1, y});
            }
        }
        if (x + 1 < n) {
            if (dist[x + 1][y] > dist[x][y] + 1) {
                dist[x + 1][y] = dist[x][y] + 1;
                q.push({x + 1, y});
            }
        }
        if (y >= 1) {
            if (dist[x][y - 1] > dist[x][y] + 1) {
                dist[x][y - 1] = dist[x][y] + 1;
                q.push({x, y - 1});
            }
        }
        if (y + 1 < n) {
            if (dist[x][y + 1] > dist[x][y] + 1) {
                dist[x][y + 1] = dist[x][y] + 1;
                q.push({x, y + 1});
            }
        }
    }
    int l = -1, r = 2 * n + 1;
    while (r - l > 1) {
        int mid = l + (r - l) / 2;
        queue<pair<int, int>> q;
        vector<vector<int>> dist2(n, vector<int>(n, 2e9));
        q.push({X, Y});
        dist2[X][Y] = mid * d;
        if (dist[X][Y] * d <= dist2[X][Y]) {
            r = mid;
            continue;
        }
        while (q.size()) {
            pair<int, int> p = q.front();
            q.pop();
            int x = p.first, y = p.second;
            if (good(x - 1, y)) {
                if (dist2[x - 1][y] > dist2[x][y] + 1 && (mas[x - 1][y] == 'D' || dist[x - 1][y] * d > dist2[x][y] + 1)) {
                    dist2[x - 1][y] = dist2[x][y] + 1;
                    q.push({x - 1, y});
                }
            }
            if (good(x + 1, y)) {
                if (dist2[x + 1][y] > dist2[x][y] + 1 && (mas[x + 1][y] == 'D' || dist[x + 1][y] * d > dist2[x][y] + 1)) {
                    dist2[x + 1][y] = dist2[x][y] + 1;
                    q.push({x + 1, y});
                }
            }
            if (good(x, y - 1)) {
                if (dist2[x][y - 1] > dist2[x][y] + 1 && (mas[x][y - 1] == 'D' || dist[x][y - 1] * d > dist2[x][y] + 1)) {
                    dist2[x][y - 1] = dist2[x][y] + 1;
                    q.push({x, y - 1});
                }
            }
            if (good(x, y + 1)) {
                if (dist2[x][y + 1] > dist2[x][y] + 1 && (mas[x][y + 1] == 'D' || dist[x][y + 1] * d > dist2[x][y] + 1)) {
                    dist2[x][y + 1] = dist2[x][y] + 1;
                    q.push({x, y + 1});
                }
            }
        }
        if (dist2[X_home][Y_home] != 2e9) {
            l = mid;
        } else {
            r = mid;
        }
    }
    cout << l;
    return;
}


signed main() {
    ll interactive = 0;
    ll multitest = 0;
    if (!interactive) {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
#ifdef LOCAL
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
#endif
    }
    if (multitest) {
        ll T;
        cin >> T;
        while (T--) {
            solve();
        }
    } else {
        solve();
    }
    return 0;
}

• Subtask 1: 39 / 100