Submission #669098

#	Time	Username	Problem	Language	Result	Execution time	Memory
669098		finn__	Mecho (IOI09_mecho)	C++17	100 / 100	353 ms	2560 KiB

mecho

#include <bits/stdc++.h>
using namespace std;

struct point
{
    size_t i, j;
};

point M, D;
vector<point> H;

inline bool is_free(char x)
{
    return x == 'G' || x == 'M';
}

void spread_bees(vector<string> &forest, queue<point> &q)
{
    queue<point> y;

    while (!q.empty())
    {
        auto const [i, j] = q.front();
        q.pop();

        if (i && is_free(forest[i - 1][j]))
        {
            forest[i - 1][j] = 'B';
            y.push({i - 1, j});
        }

        if (i < forest.size() - 1 && is_free(forest[i + 1][j]))
        {
            forest[i + 1][j] = 'B';
            y.push({i + 1, j});
        }

        if (j && is_free(forest[i][j - 1]))
        {
            forest[i][j - 1] = 'B';
            y.push({i, j - 1});
        }

        if (j < forest.size() - 1 && is_free(forest[i][j + 1]))
        {
            forest[i][j + 1] = 'B';
            y.push({i, j + 1});
        }
    }

    swap(q, y);
}

bool walk_step(
    vector<string> const &forest, vector<vector<bool>> &vis, queue<point> &p)
{
    queue<point> y;

    while (!p.empty())
    {
        auto const [i, j] = p.front();
        p.pop();

        if (is_free(forest[i][j]))
        {
            if (i && !vis[i - 1][j])
            {
                if (is_free(forest[i - 1][j]))
                {
                    vis[i - 1][j] = 1;
                    y.push({i - 1, j});
                }
                else if (forest[i - 1][j] == 'D')
                    return 1;
            }

            if (i < forest.size() - 1 && !vis[i + 1][j])
            {
                if (is_free(forest[i + 1][j]))
                {
                    vis[i + 1][j] = 1;
                    y.push({i + 1, j});
                }
                else if (forest[i + 1][j] == 'D')
                    return 1;
            }

            if (j && !vis[i][j - 1])
            {
                if (is_free(forest[i][j - 1]))
                {
                    vis[i][j - 1] = 1;
                    y.push({i, j - 1});
                }
                else if (forest[i][j - 1] == 'D')
                    return 1;
            }

            if (j < forest.size() - 1 && !vis[i][j + 1])
            {
                if (is_free(forest[i][j + 1]))
                {
                    vis[i][j + 1] = 1;
                    y.push({i, j + 1});
                }
                else if (forest[i][j + 1] == 'D')
                    return 1;
            }
        }
    }

    swap(p, y);
    return 0;
}

bool can_go_home(size_t n, size_t s, vector<string> forest, unsigned t)
{
    queue<point> p, q;
    p.push(M);
    for (point const &x : H)
        q.push(x);

    vector<vector<bool>> vis(n, vector<bool>(n, 0));
    vis[M.i][M.j] = 1;

    for (unsigned i = 0; i < t; i++)
        spread_bees(forest, q);

    while (!p.empty())
    {
        for (size_t i = 0; i < s; i++)
        {
            if (walk_step(forest, vis, p))
                return 1;
        }
        spread_bees(forest, q);
    }

    return 0;
}

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

    vector<string> forest(n);
    for (size_t i = 0; i < n; i++)
    {
        cin >> forest[i];
        for (size_t j = 0; j < n; j++)
        {
            switch (forest[i][j])
            {
            case 'M':
                M = {i, j};
                break;
            case 'D':
                D = {i, j};
                break;
            case 'H':
                H.push_back({i, j});
                break;
            }
        }
    }

    unsigned a = 0, b = n * n;
    while (a < b)
    {
        unsigned t = (a + b + 1) / 2;

        if (can_go_home(n, s, forest, t))
            a = t;
        else
            b = t - 1;
    }

    if (!a && !can_go_home(n, s, forest, 0))
        cout << -1 << '\n';
    else
        cout << a << '\n';
}

• Subtask 1: 100 / 100