Submission #654280

#	Time	Username	Problem	Language	Result	Execution time	Memory
654280		four_specks	Mecho (IOI09_mecho)	C++17	100 / 100	598 ms	2044 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 = [&]
        {
            {
                queue<array<int, 2>> q1;
                while (!q.empty())
                {
                    auto [x, y] = q.front();
                    q.pop();

                    if (!bad[x][y])
                        q1.push({x, y});
                }

                q = move(q1);
            }
            for (int i = 0; i < s && !q.empty(); 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);
            }
        };

        // auto able = [&]() -> bool
        // {
        //     vector<array<int, 2>> roll;

        //     queue q1 = q;
        //     for (int i = 0; i < s && !q1.empty(); i++)
        //     {
        //         queue<array<int, 2>> q2;
        //         while (!q1.empty())
        //         {
        //             auto [x, y] = q1.front();
        //             q1.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, q2.push({x1, y1}), roll.push_back({x, y});
        //             }
        //         }

        //         q1 = move(q2);
        //     }

        //     bool ok = seen[home[0]][home[1]];

        //     for (auto [x, y] : roll)
        //         seen[x][y] = 0;

        //     return ok;
        // };

        while (!q.empty())
        {
            // if (able())
            //     return 1;

            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: 100 / 100