Submission #1089791

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089791		_callmelucian	Maze (JOI23_ho_t3)	C++14	86 / 100	1188 ms	128520 KiB

Main

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

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

const int mn = 6e6 + 6;
int leaf[2][mn], n, m;

const int dr[4] = {-1, 0, 0, 1};
const int dc[4] = {0, -1, 1, 0};

void build (int layer, int k, int l, int r) {
    if (l == r)
        return leaf[layer][k] = l, void();
    int mid = (l + r) >> 1;
    build(layer, 2 * k, l, mid);
    build(layer, 2 * k + 1, mid + 1, r);
}

void getNode (int k, int l, int r, int a, int b, vector<int> &vec) {
    if (b < l || r < a) return;
    if (a <= l && r <= b)
        return vec.push_back(k), void();
    int mid = (l + r) >> 1;
    getNode(2 * k, l, mid, a, b, vec);
    getNode(2 * k + 1, mid + 1, r, a, b, vec);
}

int distance (int i, int j, int u, int v) {
    return max(abs(i - u), abs(j - v));
}

bool ok (int i, int j) {
    if (i < 1 || j < 1) return 0;
    if (i > n || j > m) return 0;
    return 1;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int k; cin >> n >> m >> k;
    int stx, sty, enx, eny; cin >> stx >> sty >> enx >> eny;

    vector<vector<bool>> block(n + 1, vector<bool>(m + 1));

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            char c; cin >> c;
            if (c == '#') block[i][j] = 1;
        }
    }

    build(0, 1, 1, n);
    build(1, 1, 1, m);

    vector<vector<vector<int>>> dist(3);
    dist[1] = vector<vector<int>>(4 * n, vector<int>(m + 1, INT_MAX));
    dist[2] = vector<vector<int>>(n + 1, vector<int>(4 * m, INT_MAX));
    dist[0] = vector<vector<int>>(n + 1, vector<int>(m + 1, INT_MAX));

    vector<vector<vector<bool>>> vis(3);
    vis[1] = vector<vector<bool>>(4 * n, vector<bool>(m + 1));
    vis[2] = vector<vector<bool>>(n + 1, vector<bool>(4 * m));
    vis[0] = vector<vector<bool>>(n + 1, vector<bool>(m + 1));

    deque<tt> q; q.emplace_back(0, stx, sty);
    dist[0][stx][sty] = 0;

    while (q.size()) {
        int layer, x, y; tie(layer, x, y) = q.front(); q.pop_front();
        if (vis[layer][x][y]) continue;
        vis[layer][x][y] = 1;

        function<void(int,int,int,int)> addEdge = [&] (int nlay, int nx, int ny, int w) {
            if (dist[layer][x][y] + w >= dist[nlay][nx][ny]) return;
            dist[nlay][nx][ny] = dist[layer][x][y] + w;
            if (w) q.emplace_back(nlay, nx, ny);
            else q.emplace_front(nlay, nx, ny);
        };

        if (layer == 0) {
            if (block[x][y]) {
                if (distance(x, y, enx, eny) < k)
                    return cout << dist[layer][x][y], 0;

                vector<int> nodeX, nodeY;
                int xL = max(1, x - k), xR = min(n, x + k), yL = max(1, y - k), yR = min(m, y + k);
                getNode(1, 1, n, max(1, x - k + 1), min(n, x + k - 1), nodeX);
                getNode(1, 1, m, max(1, y - k + 1), min(m, y + k - 1), nodeY);

                for (int u : nodeX) {
                    addEdge(1, u, yL, 0);
                    addEdge(1, u, yR, 0);
                }
                for (int v : nodeY) {
                    addEdge(2, xL, v, 0);
                    addEdge(2, xR, v, 0);
                }
            }
            else {
                if (distance(x, y, enx, eny) == 0)
                    return cout << dist[layer][x][y], 0;

                for (int k = 0; k < 4; k++)
                    if (ok(x + dr[k], y + dc[k]))
                        addEdge(0, x + dr[k], y + dc[k], block[x + dr[k]][y + dc[k]]);
            }
        }
        else if (layer == 1) {
            if (leaf[0][x]) addEdge(0, leaf[0][x], y, block[leaf[0][x]][y]);
            else {
                addEdge(1, 2 * x, y, 0);
                addEdge(1, 2 * x + 1, y, 0);
            }
        }
        else if (layer == 2) {
            if (leaf[1][y]) addEdge(0, x, leaf[1][y], block[x][leaf[1][y]]);
            else {
                addEdge(2, x, 2 * y, 0);
                addEdge(2, x, 2 * y + 1, 0);
            }
        }
    }
    cout << -1;

    return 0;
}

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