Submission #1115454

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115454		_callmelucian	Maze (JOI23_ho_t3)	C++14	100 / 100	1944 ms	1451960 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> tpl;

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

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

int n, m, k, stx, sty, enx, eny;
vector<vector<int>> toL, toR, toU, toD, dist;
vector<vector<bool>> vis;
vector<vector<char>> ch;
deque<pii> q;

struct DSU {
    vector<int> lab, lo, hi;
    DSU (int sz) : lab(sz + 1, -1), lo(sz + 1), hi(sz + 1) {}

    int get (int u) {
        if (lab[u] < 0) return u;
        return lab[u] = get(lab[u]);
    }

    void asgn (int u, int val) {
        assert(lab[u] < 0);
        lo[u] = hi[u] = val;
    }

    int getLo (int u) { return lo[get(u)]; }
    int getHi (int u) { return hi[get(u)]; }

    void unite (int a, int b) {
        a = get(a), b = get(b);
        if (a == b) return;
        if (-lab[a] < -lab[b]) swap(a, b);
        lab[a] += lab[b], lab[b] = a;
        lo[a] = min(lo[a], lo[b]), hi[a] = max(hi[a], hi[b]);
    }
};

vector<DSU> dsuCol, dsuRow;

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

void removeCell (int i, int j, int d) {
//    cout << "remove cell " << i << " " << j << " " << d << "\n";
    if (vis[i][j]) return;
    if (ch[i][j] == '#') q.emplace_back(i, j), dist[i][j] = d + 1;
    else q.emplace_front(i, j), dist[i][j] = d;
    vis[i][j] = 1;

    if (ok(i, toL[i][j])) toR[i][toL[i][j]] = toR[i][j];
    if (ok(i, toR[i][j])) toL[i][toR[i][j]] = toL[i][j];
    if (ok(toU[i][j], j)) toD[toU[i][j]][j] = toD[i][j];
    if (ok(toD[i][j], j)) toU[toD[i][j]][j] = toU[i][j];

    dsuRow[i].asgn(j, j);
    if (j + 1 <= m && dsuRow[i].getHi(j + 1)) dsuRow[i].unite(j, j + 1);
    if (j - 1 >= 1 && dsuRow[i].getLo(j - 1)) dsuRow[i].unite(j - 1, j);

    dsuCol[j].asgn(i, i);
    if (i + 1 <= n && dsuCol[j].getHi(i + 1)) dsuCol[j].unite(i, i + 1);
    if (i - 1 >= 1 && dsuCol[j].getLo(i - 1)) dsuCol[j].unite(i - 1, i);
}

void transitionRow (int row, int initCol, int d) {
    int prv = dsuRow[row].getLo(initCol), nxt = dsuRow[row].getHi(initCol);
    for (int col = (!prv ? initCol : prv - 1); col >= max(1, initCol - k + 1); col = toL[row][col]) removeCell(row, col, d);
    for (int col = (!nxt ? initCol : nxt + 1); col <= min(m, initCol + k - 1); col = toR[row][col]) removeCell(row, col, d);
}

void transitionCol (int initRow, int col, int d) {
    int prv = dsuCol[col].getLo(initRow), nxt = dsuCol[col].getHi(initRow);
    for (int row = (!prv ? initRow : prv - 1); row >= max(1, initRow - k + 1); row = toU[row][col]) removeCell(row, col, d);
    for (int row = (!nxt ? initRow : nxt + 1); row <= min(n, initRow + k - 1); row = toD[row][col]) removeCell(row, col, d);
}

int distance (int i, int j, int x, int y) {
    return max(abs(i - x), abs(j - y));
}

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

    // read input + initialization
    cin >> n >> m >> k;
    cin >> stx >> sty >> enx >> eny;

    ch = vector<vector<char>>(n + 1, vector<char>(m + 1));
    toL = toR = toU = toD = dist = vector<vector<int>>(n + 1, vector<int>(m + 1));
    vis = vector<vector<bool>>(n + 1, vector<bool>(m + 1));
    dsuCol = vector<DSU>(m + 1, DSU(n));
    dsuRow = vector<DSU>(n + 1, DSU(m));

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> ch[i][j];
            toL[i][j] = j - 1, toR[i][j] = j + 1;
            toU[i][j] = i - 1, toD[i][j] = i + 1;
        }
    }

    // setup BFS + run
    removeCell(stx, sty, 0);
    while (q.size()) {
        int i, j; tie(i, j) = q.front(); q.pop_front();
        if (ch[i][j] == '#' && distance(i, j, enx, eny) < k)
            return cout << dist[i][j], 0;
        if (i == enx && j == eny)
            return cout << dist[i][j], 0;

//        cout << "visiting " << i << " " << j << " " << dist[i][j] << "\n";

        if (ch[i][j] == '#') {
            if (1 <= i - k) transitionRow(i - k, j, dist[i][j]);
            if (i + k <= n) transitionRow(i + k, j, dist[i][j]);
            if (1 <= j - k) transitionCol(i, j - k, dist[i][j]);
            if (j + k <= m) transitionCol(i, j + k, dist[i][j]);
        }
        else {
            for (int it = 0; it < 4; it++) {
                int i2 = i + dr[it], j2 = j + dc[it];
                if (ok(i2, j2) && !vis[i2][j2]) removeCell(i2, j2, dist[i][j]);
            }
        }
    }

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