Submission #769097

#	Time	Username	Problem	Language	Result	Execution time	Memory
769097		danikoynov	Maze (JOI23_ho_t3)	C++14	51 / 100	2073 ms	37152 KiB

Main

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 6e6 + 10, block = sqrt(maxn) + 10;

struct cell
{
    int x, y;

    cell(int _x = 0, int _y = 0)
    {
        x = _x;
        y = _y;
    }

    cell add(const cell &r) const
    {
        cell d;
        d.x = x + r.x;
        d.y = y + r.y;
        return d;
    }
};

cell neib[4] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};

int n, m, h;

vector < int > a[block], par[block];
vector < int > l[block], r[block];
vector < int > used[block];

int stx, sty, enx, eny;

int find_leader(int i, int j)
{
    if (par[i][j] == j)
        return j;
    return (par[i][j] = find_leader(i, par[i][j]));
}

void unite(int x, int y, int i, int j)
{
    y = find_leader(x, y);
    j = find_leader(i, j);
    if (y == j)
        return;
    l[i][j] = min(l[i][j], l[x][y]);
    r[i][j] = max(r[i][j], r[x][y]);
    par[x][y] = j;
}
void solve()
{
    cin >> n >> m >> h;
    cin >> stx >> sty;
    cin >> enx >> eny;
    for (int i = 1; i <= n; i ++)
    {
        a[i].resize(m + 2);
        l[i].resize(m + 2);
        r[i].resize(m + 2);
        par[i].resize(m + 2);
        used[i].resize(m + 2);
        for (int j = 1; j <= m; j ++)
        {
            l[i][j] = r[i][j] = j;
            par[i][j] = j;
            used[i][j] = -1;
        }

        for (int j = 1; j <= m; j ++)
        {
            char c;
            cin >> c;
            if (c == '.')
                a[i][j] = 0;
            else
                a[i][j] = 1;
        }
    }

    deque < cell > q;
    q.push_back(cell(stx, sty));
    used[stx][sty] = 0;
    while(!q.empty())
    {
        cell cur = q.front();
        q.pop_front();
        /**cout << cur.x << " : " << cur.y << " " << used[cur.x][cur.y] << endl;
        for (int i = 1; i <= n; i ++, cout << endl)
            for (int j = 1; j <= m; j ++)
                cout << used[i][j] << " ";*/

        for (int i = 0; i < 4; i ++)
        {
            cell nb = cur.add(neib[i]);
            ///cout << nb.x << " --- " << nb.y << endl;

            if (nb.x > 0 && nb.x <= n && nb.y > 0 && nb.y <= m)
            {
                if (used[nb.x][nb.y] == -1 && a[nb.x][nb.y] == 0)
                {

                    used[nb.x][nb.y] = used[cur.x][cur.y];
                    q.push_front(nb);
                }
            }
        }

        int left = max(1, cur.y - h), right = min(m, cur.y + h);

        for (int i = max(1, cur.x - h); i <= min(n, cur.x + h); i ++)
        {
            if (i == cur.x - h || i == cur.x + h)
                left ++, right --;
            if (a[i][left] == 1)
            {
                used[i][left] = used[cur.x][cur.y] + 1;
                q.push_back(cell(i, left));
                a[i][left] = 0;
                if (left > 1 && a[i][left - 1] == 0)
                    unite(i, left, i, left - 1);
                if (left < m && a[i][left + 1] == 0)
                    unite(i, left, i, left + 1);
            }

            while(true)
            {
                ///cout << "cycle " << i << " " << left << " " << right << endl;
                int lead = find_leader(i, left), to = r[i][lead];
                ///cout << lead << " " << r[i][lead] << endl;
                if (to < right)
                {
                    if (a[i][to + 1] == 1)
                    {
                        used[i][to + 1] = used[cur.x][cur.y] + 1;
                        q.push_back(cell(i, to + 1));
                        a[i][to + 1] = 0;
                    }
                    unite(i, to, i, to + 1);

                }
                else
                {
                    break;
                }
            }

                        if (i == cur.x - h || i == cur.x + h)
                left --, right ++;
        }
    }


    cout << used[enx][eny] << endl;

}

int main()
{
    solve();
    return 0;
}

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