Submission #953335

#	Time	Username	Problem	Language	Result	Execution time	Memory
953335		snowman	Mecho (IOI09_mecho)	C++17	51 / 100	269 ms	6484 KiB

mecho

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

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

bool valid(int x, int y, int n) {
    return x >= 0 && x < n && y >= 0 && y < n;
}

bool canReachHome(int start_x, int start_y, int finish_x, int finish_y, int mid, int s, const vector<vector<int>>& bees, const vector<vector<char>>& mapa) {
    vector<vector<int>> h(mapa.size(), vector<int>(mapa.size(), INT_MAX));
    h[start_x][start_y] = mid;
    queue<pair<int,int>> q;
    q.push({start_x, start_y});

    while (!q.empty()) {
        pair<int, int> u = q.front();
        q.pop();

        if (u.first == finish_x && u.second == finish_y) return true;

        for (int i = 0; i < 4; i++) {
            int nx = u.first + dx[i];
            int ny = u.second + dy[i];
            if (valid(nx, ny, mapa.size()) && mapa[nx][ny] != 'T' && h[u.first][u.second] + 1 < bees[nx][ny] && h[u.first][u.second] + 1 < h[nx][ny]) {
                q.push({nx, ny});
                h[nx][ny] = h[u.first][u.second] + 1;
            }
        }
    }
    return false;
}

int main() {
    int n, s;
    cin >> n >> s;

    vector<vector<char>> mapa(n, vector<char>(n));
    vector<pair<int,int>> hives;
    pair<int, int> start, finish;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            char x;
            cin >> x;
            if (x == 'H') hives.push_back({i, j});
            if (x == 'M') start = {i, j};
            if (x == 'D') finish = {i, j};
            mapa[i][j] = x;
        }
    }

    vector<vector<int>> bees(n, vector<int>(n, INT_MAX));
    queue<pair<int, int>> qB;

    for (auto hive : hives) {
        bees[hive.first][hive.second] = 0;
        qB.push(hive);
    }

    while (!qB.empty()) {
        pair<int, int> u = qB.front();
        qB.pop();

        for (int i = 0; i < 4; i++) {
            int nx = u.first + dx[i];
            int ny = u.second + dy[i];
            if (valid(nx, ny, n) && mapa[nx][ny] == 'G' && bees[u.first][u.second] + s < bees[nx][ny]) {
                qB.push({nx, ny});
                bees[nx][ny] = bees[u.first][u.second] + s;
            }
        }
    }

    int l = 0, r = n * n * 2;
    int ans = -1;

    while (l <= r) {
        int mid = (l + r) / 2;
        if (canReachHome(start.first, start.second, finish.first, finish.second, mid, s, bees, mapa)) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }

    if (ans == -1) {
        cout << -1 << '\n';
    } else {
        cout << ans / s << '\n';
    }

    return 0;
}

• Subtask 1: 51 / 100