Submission #654276

#	Time	Username	Problem	Language	Result	Execution time	Memory
654276		four_specks	Mecho (IOI09_mecho)	C++17	54 / 100	614 ms	2344 KiB

mecho

#include <bits/stdc++.h>

using namespace std;

inline namespace
{
} // namespace

void solve()
{
    int n, s;
    cin >> n >> s;

    vector<string> grid(n);
    for (string &row : grid)
        cin >> row;

    vector grass(n, vector<bool>(n, 1));
    vector<array<int, 2>> hives;
    array<int, 2> honey, home;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            char cell = grid[i][j];
            if (cell == 'T')
                grass[i][j] = 0;
            else if (cell == 'M')
                honey = {i, j};
            else if (cell == 'D')
                home = {i, j};
            else if (cell == 'H')
                hives.push_back({i, j});
        }
    }

    auto check = [&](int mid) -> bool
    {
        vector bad(n, vector<bool>(n, 0));
        queue<array<int, 2>> bees;
        for (const array<int, 2> &coord : hives)
            bad[coord[0]][coord[1]] = 1, bees.push(coord);

        auto mv_bees = [&]
        {
            queue<array<int, 2>> bees1;
            while (!bees.empty())
            {
                auto [x, y] = bees.front();
                bees.pop();

                for (auto [dx, dy] : {array{0, -1}, array{0, 1}, array{-1, 0}, array{1, 0}})
                {
                    int x1 = x + dx, y1 = y + dy;
                    if (0 <= x1 && x1 < n && 0 <= y1 && y1 < n && grass[x1][y1] && array{x1, y1} != home && !bad[x1][y1])
                        bad[x1][y1] = 1, bees1.push({x1, y1});
                }
            }

            bees = move(bees1);
        };

        for (int i = 0; i < mid; i++)
            mv_bees();

        vector seen(n, vector<bool>(n, 0));
        queue<array<int, 2>> q;
        if (!bad[honey[0]][honey[1]])
            seen[honey[0]][honey[1]] = 1, q.push(honey);

        auto mv_q = [&]
        {
            for (int i = 0; i < s; i++)
            {
                queue<array<int, 2>> q1;
                while (!q.empty())
                {
                    auto [x, y] = q.front();
                    q.pop();

                    for (auto [dx, dy] : {array{0, -1}, array{0, 1}, array{-1, 0}, array{1, 0}})
                    {
                        int x1 = x + dx, y1 = y + dy;
                        if (0 <= x1 && x1 < n && 0 <= y1 && y1 < n && grass[x1][y1] && !bad[x1][y1] && !seen[x1][y1])
                            seen[x1][y1] = 1, q1.push({x1, y1});
                    }
                }

                q = move(q1);
            }
        };

        while (!q.empty())
        {
            mv_q();
            mv_bees();
        }

        return seen[home[0]][home[1]];
    };

    int lo = -1, hi = n * n;
    while (lo < hi)
    {
        int mid = (lo + hi + 1) / 2;
        if (check(mid))
            lo = mid;
        else
            hi = mid - 1;
    }

    cout << lo << '\n';
}

int main()
{
    ios_base::sync_with_stdio(false), cin.tie(NULL);

    solve();

    return 0;
}

• Subtask 1: 54 / 100