Submission #885004

#	Time	Username	Problem	Language	Result	Execution time	Memory
885004		Alcabel	Maze (JOI23_ho_t3)	C++17	100 / 100	1790 ms	155220 KiB

Main

#pragma GCC optimize("O3", "Ofast", "unroll-loops")
// #pragma GCC target("avx", "avx2")
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;

const int inf = 1e7;
const pair<int, int> deltas[4] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
vector<string> a;
vector<vector<int>> vis, dist;
int r, c, mini, minj, maxi, maxj, tt;
vector<pair<int, int>> q;

void dfs(int i, int j) {
    q.emplace_back(i, j);
    vis[i][j] = tt;
    for (const auto& [di, dj] : deltas) {
        int newi = i + di, newj = j + dj;
        if (newi >= mini && newi <= maxi && newj >= minj && newj <= maxj && vis[newi][newj] < tt && dist[newi][newj] >= dist[i][j]) {
            dist[newi][newj] = dist[i][j];
            dfs(newi, newj);
        }
    }
}

void solve() {
    int n;
    cin >> r >> c >> n;
    int sr, sc, gr, gc;
    cin >> sr >> sc >> gr >> gc;
    --sr, --sc, --gr, --gc;
    a.resize(r);
    for (int i = 0; i < r; ++i) {
        cin >> a[i];
    }
    vis.resize(r, vector<int>(c, -1));
    dist.resize(r, vector<int>(c, inf));
    vector<vector<int>> nxt(r, vector<int>(c, -1));
    vector<pair<int, int>> ext;
    dist[sr][sc] = 0;
    q.emplace_back(sr, sc);
    tt = -1;
    ext.reserve(r * c);
    q.reserve(r * c);
    while (dist[gr][gc] == inf) {
        ++tt;
        while (!q.empty()) {
            auto [i, j] = q.back();
            q.pop_back();
            if (vis[i][j] == tt) {
                continue;
            }
            vis[i][j] = tt;
            ext.emplace_back(i, j);
            if ((i - n <= gr && gr <= i + n && j - n + 1 <= gc && gc <= j + n - 1) || (i - n + 1 <= gr && gr <= i + n - 1 && j - n <= gc && gc <= j + n)) {
                dist[gr][gc] = min(dist[gr][gc], dist[i][j] + 1);
            }
            for (const auto& [di, dj] : deltas) {
                int newi = i + di, newj = j + dj;
                if (newi >= 0 && newi < r && newj >= 0 && newj < c && a[newi][newj] == '.' && dist[newi][newj] > dist[i][j]) {
                    dist[newi][newj] = dist[i][j];
                    q.emplace_back(newi, newj);
                }
            }
        }
        if (dist[gr][gc] != inf) {
            break;
        }
        for (int iter = 0; iter < 4; ++iter) {
            ++tt;
            sort(ext.begin(), ext.end());
            if (iter == 0) {
                // up
                int lastI = -1, start = -1;
                pair<int, int> segj = {0, -1};
                bool sameI;
                for (auto [i, j] : ext) {
                    sameI = (lastI == i);
                    if (lastI == i && segj.second + 1 == j) {
                        ++segj.second;
                    } else {
                        for (int k = segj.first; k <= segj.second; ++k) {
                            nxt[lastI][k] = segj.second + 1;
                        }
                        lastI = i, segj = {j, j};
                    }
                    mini = max(0, i - n), minj = max(0, j - n + 1);
                    maxi = min(r - 1, i - 1), maxj = min(c - 1, j + n - 1);
                    if (i - 1 >= 0) {
                        int newD = dist[i][j] + 1;
                        if (sameI) {
                            j = max(j, start);
                        }
                        start = maxj + 1;
                        --i;
                        if (j <= maxj && dist[i][j] == newD - 1) {
                            j = nxt[i][j];
                        }
                        if (j <= maxj && dist[i][j] > newD - 1) {
                            dist[i][j] = newD;
                            dfs(i, j);
                        }
                    }
                }
            } else if (iter == 1) {
                // left
                int lastJ = -1, start = -1;
                pair<int, int> segi = {0, -1};
                bool sameJ;
                for (auto [j, i] : ext) {
                    i = -i;
                    sameJ = (lastJ == j);
                    if (lastJ == j && segi.first - 1 == i) {
                        --segi.first;
                    } else {
                        for (int k = segi.first; k <= segi.second; ++k) {
                            nxt[k][lastJ] = segi.first - 1;
                        }
                        lastJ = j, segi = {i, i};
                    }
                    mini = max(0, i - n + 1), minj = max(0, j - n);
                    maxi = min(r - 1, i + n - 1), maxj = min(c - 1, j - 1);
                    if (j - 1 >= 0) {
                        int newD = dist[i][j] + 1;
                        if (sameJ) {
                            i = min(i, start);
                        }
                        start = mini - 1;
                        --j;
                        if (i >= mini && dist[i][j] == newD - 1) {
                            i = nxt[i][j];
                        }
                        if (i >= mini && dist[i][j] > newD - 1) {
                            dist[i][j] = newD;
                            dfs(i, j);
                        }
                    }
                }
            } else if (iter == 2) {
                // down
                int lastI = -1, start = -1;
                pair<int, int> segj = {0, -1};
                bool sameI;
                for (auto [i, j] : ext) {
                    i = -i, j = -j;
                    sameI = (lastI == i);
                    if (lastI == i && segj.first - 1 == j) {
                        --segj.first;
                    } else {
                        for (int k = segj.first; k <= segj.second; ++k) {
                            nxt[lastI][k] = segj.first - 1;
                        }
                        lastI = i, segj = {j, j};
                    }
                    mini = max(0, i + 1), minj = max(0, j - n + 1);
                    maxi = min(r - 1, i + n), maxj = min(c - 1, j + n - 1);
                    if (i + 1 < r) {
                        int newD = dist[i][j] + 1;
                        if (sameI) {
                            j = min(j, start);
                        }
                        start = minj - 1;
                        ++i;
                        if (j >= minj && dist[i][j] == newD - 1) {
                            j = nxt[i][j];
                        }
                        if (j >= minj && dist[i][j] > newD - 1) {
                            dist[i][j] = newD;
                            dfs(i, j);
                        }
                    }
                }
            } else {
                // right
                int lastJ = -1, start = -1;
                pair<int, int> segi = {0, -1};
                bool sameJ;
                for (auto [j, i] : ext) {
                    j = -j;
                    sameJ = (lastJ == j);
                    if (lastJ == j && segi.second + 1 == i) {
                        ++segi.second;
                    } else {
                        for (int k = segi.first; k <= segi.second; ++k) {
                            nxt[k][lastJ] = segi.second + 1;
                        }
                        lastJ = j, segi = {i, i};
                    }
                    mini = max(0, i - n + 1), minj = max(0, j + 1);
                    maxi = min(r - 1, i + n - 1), maxj = min(c - 1, j + n);
                    if (j + 1 < c) {
                        int newD = dist[i][j] + 1;
                        if (sameJ) {
                            i = max(i, start);
                        }
                        start = maxi + 1;
                        ++j;
                        if (i <= maxi && dist[i][j] == newD - 1) {
                            i = nxt[i][j];
                        }
                        if (i <= maxi && dist[i][j] > newD - 1) {
                            dist[i][j] = newD;
                            dfs(i, j);
                        }
                    }
                }
            }
            for (int i = 0; i < (int)ext.size(); ++i) {
                ext[i].first = -ext[i].first;
                swap(ext[i].first, ext[i].second);
            }
        }
        ext.clear();
    }
    cout << dist[gr][gc] << '\n';
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
        cerr << "-----------\n";
        cout << "-----------\n";
    }
#else
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
#endif

    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