Submission #1161342

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161342		Der_Vlapos	Maze (JOI23_ho_t3)	C++20	100 / 100	488 ms	100448 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pii pair<int, int>
#define f first
#define s second
#define all(v) v.begin(), v.end()
#define pb push_back

const int BIG = 1e9 + 10;

struct test
{
    void solve()
    {
        int n, m, k;
        cin >> n >> m >> k;
        int x1 = 0, y1 = 0, x2 = 0, y2 = 0;
        cin >> x1 >> y1 >> x2 >> y2;
        --x1, --y1;
        --x2, --y2;

        vector<vector<bool>> f(n, vector<bool>(m));
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
            {
                char x;
                cin >> x;
                f[i][j] = x == '.';
            }
        queue<pii> els;
        vector<vector<bool>> was(n, vector<bool>(m, 0));
        els.push({x1, y1});
        was[x1][y1] = 1;

        const int dx4[4] = {-1, 0, 0, 1};
        const int dy4[4] = {0, 1, -1, 0};
        const int dx8[8] = {-1, 0, 0, 1, -1, -1, 1, 1};
        const int dy8[8] = {0, 1, -1, 0, -1, 1, -1, 1};

        auto good = [&](int x, int y) -> bool
        { return x >= 0 and y >= 0 and x < n and y < m; };

        int CNT = 0;
        while (!was[x2][y2])
        {
            // go through white
            queue<pair<pii, int>> adjacent_black;

            while (els.size())
            {
                auto [x, y] = els.front();
                els.pop();
                for (int d = 0; d < 4; ++d)
                {
                    int tox = x + dx4[d];
                    int toy = y + dy4[d];
                    if (good(tox, toy) and !was[tox][toy])
                    {
                        if (f[tox][toy])
                            els.push({tox, toy});
                        else
                        {
                            adjacent_black.push({{tox, toy}, k});
                        }
                        was[tox][toy] = 1;
                    }
                }
            }

            if (was[x2][y2])
                break;
            CNT++;

            queue<pii> newels;
            while (adjacent_black.size())
            {
                auto [c, D] = adjacent_black.front();
                adjacent_black.pop();
                auto [x, y] = c;

                if (D)
                {
                    f[x][y] = 1;
                    newels.push({x, y});
                }
                else
                {
                    if (f[x][y])
                        newels.push({x, y});
                    else
                        was[x][y] = 0;
                    continue;
                }
                if (D > 1)
                    for (int d = 0; d < 8; ++d)
                    {
                        int tox = x + dx8[d];
                        int toy = y + dy8[d];
                        if (good(tox, toy) and !was[tox][toy])
                        {
                            adjacent_black.push({{tox, toy}, D - 1});
                            was[tox][toy] = 1;
                        }
                    }
                else
                {
                    for (int d = 0; d < 4; ++d)
                    {
                        int tox = x + dx4[d];
                        int toy = y + dy4[d];
                        if (good(tox, toy) and !was[tox][toy])
                        {
                            adjacent_black.push({{tox, toy}, D - 1});
                            was[tox][toy] = 1;
                        }
                    }
                }
            }
            els = newels;
            // for (int i = 0; i < n; ++i, cerr << "\n")
            //     for (int j = 0; j < m; ++j)
            //         cerr << was[i][j] << " ";
            // cerr << "\n";
        }
        cout << CNT << "\n";
    }
};

main()
{
    test t;
    t.solve();
}

Compilation message (stderr)

Main.cpp:132:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  132 | main()
      | ^~~~

• Subtask 1: 8 / 8
• Subtask 2: 19 / 19
• Subtask 3: 16 / 16
• Subtask 4: 19 / 19
• Subtask 5: 5 / 5
• Subtask 6: 19 / 19
• Subtask 7: 8 / 8
• Subtask 8: 6 / 6