Submission #810849

#	Time	Username	Problem	Language	Result	Execution time	Memory
810849		_martynas	Maze (JOI23_ho_t3)	C++11	51 / 100	2086 ms	307072 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define all(a) (a).begin(), (a).end()

using pii = pair<int, int>;

const int inf = 1e7;

int r, c, n;
int sr, sc, gr, gc;
vector<string> A;

int main() {
    cin >> r >> c >> n;
    if(c > r) {
        swap(r, c);
        cin >> sc >> sr >> gc >> gr;
        A = vector<string>(r, string(c, '#'));
        for(int i = 0; i < c; i++) {
            string s; cin >> s;
            for(int j = 0; j < r; j++) {
                A[j][i] = s[j];
            }
        }
    }
    else {
        cin >> sr >> sc >> gr >> gc;
        A = vector<string>(r);
        for(int i = 0; i < c; i++) {
            cin >> A[i]; 
        }
    }
    sr--, sc--, gr--, gc--;

    // cerr << "\n";
    // for(int i = 0; i < r; i++) {
    //     cerr << A[i] << "\n";
    // }

    // c < 2500
    vector<vector<int>> dist(r, vector<int>(c, inf));
    vector<vector<bool>> visited(r, vector<bool>(c));
    vector<set<int>> checked(c);
    deque<pii> deq;
    vector<pii> dir{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    auto transition = [&](int row, int s, int e, int d) {
        //cerr << "transit: " << row << " " << s << " " << e << " " << d << "\n";
        for(int i = s; i <= e; i++) {
            // if(dist[row][i] <= d+1) break;
            if(dist[row][i] > d+1) {
                dist[row][i] = d+1;
                deq.push_back({row, i});
            }
        }
        for(int i = e; i >= s; i--) {
            //if(dist[row][i] <= d+1) break;
            if(dist[row][i] > d+1) {
                dist[row][i] = d+1;
                deq.push_back({row, i});
            }
        }
    };

    dist[sr][sc] = 0;
    deq.push_back({sr, sc});
    while(!deq.empty()) {
        int i = deq.front().fi, j = deq.front().se;
        deq.pop_front();
        if(visited[i][j]) continue;
        visited[i][j] = true;
        for(auto d : dir) {
            int ii = i+d.fi, jj = j+d.se;
            if(ii < 0 || ii >= r || jj < 0 || jj >= c) continue;
            if(A[ii][jj] == '.' && dist[ii][jj] > dist[i][j]) {
                dist[ii][jj] = dist[i][j];
                deq.push_front({ii, jj});
            }
        }
        int li = max(0, i-(n-1)), ri = min(r-1, i+(n-1));
        if(!checked[j].empty()) {
            auto it = checked[j].lower_bound(i);
            if(it == checked[j].end()) {
                it = prev(it);
                li = max(li, (*it)+n);
            }
            else {
                ri = min(ri, (*it)-n);
                if(it != checked[j].begin()) {
                    it = prev(it);
                    li = max(li, (*it)+n);   
                }
            }
        }
        checked[j].insert(i);
        if(li <= ri) {
            for(int row = li; row <= ri; row++) {
                transition(row, max(0, j-n), min(c-1, j+n), dist[i][j]);
            }
        }
        if(i-n >= 0) {
            transition(i-n, max(0, j-n+1), min(c-1, j+n-1), dist[i][j]);
        }
        if(i+n < r) {
            transition(i+n, max(0, j-n+1), min(c-1, j+n-1), dist[i][j]);
        }
    }
    cout << dist[gr][gc] << "\n";
    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