Submission #810810

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
810810	2023-08-06T15:42:41 Z	_martynas	Maze (JOI23_ho_t3)	C++17	0 / 100	2000 ms	996084 KB

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--;
    // c < 2500
    vector<vector<int>> dist(r, vector<int>(c, inf));
    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) {
        for(int i = s; i <= e; i++) {
            if(dist[row][i] <= d) break;
            dist[row][i] = d+1;
            deq.push_back({row, i});
        }
        for(int i = e; i >= s; i--) {
            if(dist[row][i] <= d) break;
            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();
        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(n-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
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	296 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Execution timed out	2106 ms	340056 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-

Subtask #2
0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Execution timed out	2110 ms	332924 KB	Time limit exceeded
6	Halted	0 ms	0 KB	-

Subtask #3
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	300 KB	Output is correct
9	Correct	3 ms	808 KB	Output is correct
10	Correct	1 ms	300 KB	Output is correct
11	Correct	1 ms	300 KB	Output is correct
12	Correct	1 ms	352 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	5 ms	552 KB	Output is correct
15	Correct	179 ms	17500 KB	Output is correct
16	Correct	114 ms	9596 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	1 ms	296 KB	Output is correct
19	Correct	0 ms	212 KB	Output is correct
20	Correct	1 ms	212 KB	Output is correct
21	Execution timed out	2122 ms	996084 KB	Time limit exceeded
22	Halted	0 ms	0 KB	-

Subtask #4
0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Execution timed out	2110 ms	332924 KB	Time limit exceeded
6	Halted	0 ms	0 KB	-

Subtask #5
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Execution timed out	2110 ms	332924 KB	Time limit exceeded
6	Halted	0 ms	0 KB	-

Subtask #6
0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	296 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Execution timed out	2106 ms	340056 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-

Subtask #7
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	296 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Execution timed out	2106 ms	340056 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-

Subtask #8
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	296 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Execution timed out	2106 ms	340056 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-

Submission #810810

Compilation message