Submission #769484

#	Time	Username	Problem	Language	Result	Execution time	Memory
769484		danikoynov	Maze (JOI23_ho_t3)	C++14	43 / 100	325 ms	189056 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 = 1.5e6 + 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], fict[block];
vector < int > used[block], ver_idx[block];

vector < pair < int, int > > adj[maxn];

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;
}



int nxt;

int build(int row, int left, int right)
{
    if (left == right)
        return ver_idx[row][left];

    int mid = (left + right) / 2;
    int lf = build(row, left, mid);
    int rf = build(row, mid + 1, right);
    nxt ++;
    adj[nxt].push_back({lf, 0});
    adj[nxt].push_back({rf, 0});
    return nxt;
}

void add_edges(int root, int left, int right, int qleft, int qright, int ver, int val)
{
    if (left > qright || right < qleft)
        return;
    if (left >= qleft && right <= qright)
    {
        adj[ver].push_back({root, val});
        return;
    }

    int mid = (left + right) / 2;
    add_edges(adj[root][0].first, left, mid, qleft, qright, ver, val);
    add_edges(adj[root][1].first, mid + 1, right, qleft, qright, ver, val);
}

int row_root[block];

int visit[maxn], dist[maxn];


int col_root[maxn];
int build_col(int col, int left, int right)
{
    if (left == right)
        return fict[left][col];

    int mid = (left + right) / 2;
    int lf = build_col(col, left, mid);
    int rf = build_col(col, mid + 1, right);
    nxt ++;
    adj[nxt].push_back({lf, 0});
    adj[nxt].push_back({rf, 0});
    return nxt;
}

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);
        fict[i].resize(m + 2);
        ver_idx[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;
        }
    }

    int cnt = 0;
    nxt = n * m;
    for (int i = 1; i <= n; i ++)
    {
        for (int j = 1; j <= m; j ++)
        {
            ver_idx[i][j] = ++ cnt;
        }
    }

    for (int i = 1; i <= n; i ++)
        row_root[i] = build(i, 1, m);

    for (int j = 1; j <= m; j ++)
    {

        for (int i = 1; i <= n; i ++)
        {

            int left = max(1, j - h), right = min(m, j + h);
            fict[i][j] = ++ nxt;
            add_edges(row_root[i], 1, m, left, right, fict[i][j], 0);
        }
        /**for (int i = 1; i <= n; i ++)
            cout << fict[i][j] << " ";
        cout << endl;*/
        col_root[j] = build_col(j, 1, n);
    }
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
        {
            cell cur(i, j);
            for (int d = 0; d < 4; d ++)
            {
                cell nb = cur.add(neib[d]);
                if (nb.x > 0 && nb.x <= n && nb.y > 0 && nb.y <= m)
                    if (a[nb.x][nb.y] == 0)
                    {
                        adj[ver_idx[cur.x][cur.y]].push_back({ver_idx[nb.x][nb.y], 0});
                    }
            }

            int st_row = max(1, i - h), en_row = min(n, i + h);
            int st_col = max(1, j - h), en_col = min(m, j + h);
            int fs_row = st_row, ds_row = en_row;
            if (fs_row == i - h)
                fs_row ++;
            if (ds_row == i + h)
                ds_row --;
                ///cout << i << " " << j << " range " << st_row << " " << en_row << endl;
            add_edges(col_root[j], 1, n, fs_row, ds_row, ver_idx[i][j], 1);

            if (st_row == i - h)
            {
                if (st_col == j - h)
                    st_col ++;
                if (en_col == j + h)
                    en_col --;
                add_edges(row_root[st_row], 1, m, st_col, en_col, ver_idx[i][j], 1);
                if (st_col == j - h)
                    st_col --;
                if (en_col == j + h)
                    en_col ++;
            }
            if (en_row == i + h)
            {
                if (st_col == j - h)
                    st_col ++;
                if (en_col == j + h)
                    en_col --;
                ////cout << i << " " << j << " range " << st_col << " " << en_col << endl;
                add_edges(row_root[en_row], 1, m, st_col, en_col, ver_idx[i][j], 1);
                if (st_col == j - h)
                    st_col --;
                if (en_col == j + h)
                    en_col ++;
            }
            /**for (int row = st_row; row <= en_row; row ++)
            {
                if (row == i - h || row == i + h)
                {
                    st_col ++, en_col --;

                    add_edges(row_root[row], 1, m, st_col, en_col, ver_idx[i][j], 1);
                    st_col --, en_col ++;
                }
                else
                {
                    adj[ver_idx[cur.x][cur.y]].push_back({fict[row][cur.y], 1});
                }
            }*/
        }


    for (int i = 1; i <= nxt; i ++)
        dist[i] = 1e9;

    deque < int > dq;
    dq.push_back(ver_idx[stx][sty]);
    dist[ver_idx[stx][sty]] = 0;
    while(!dq.empty())
    {
        int cur = dq.front();
        dq.pop_front();
        for (pair < int, int > nb : adj[cur])
        {
            int u = nb.first;
            int w = nb.second;
            if (dist[u] > dist[cur] + w)
            {
                dist[u] = dist[cur] + w;
                if (w == 0)
                    dq.push_front(u);
                else
                    dq.push_back(u);
            }
        }
    }
    /**for (int i = 1; i <= n; i ++, cout << endl)
        for (int j = 1; j <= m; j ++)
            cout << dist[ver_idx[i][j]] << " ";*/
    cout << dist[ver_idx[enx][eny]] << endl;


}

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

• Subtask 1: 0 / 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