oj.uz

Submission #810821

# Submission time Handle Problem Language Result Execution time Memory
810821 2023-08-06T15:51:32 Z _martynas Maze (JOI23_ho_t3) C++11
0 / 100
 2000 ms 994700 KB 
#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<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) {
        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();
        // 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(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 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Execution timed out 2089 ms 336088 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 19.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 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Execution timed out 2096 ms 333740 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 0 ms 212 KB Output is correct
4 Correct 0 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 0 ms 340 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 3 ms 724 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 4 ms 468 KB Output is correct
15 Correct 182 ms 17436 KB Output is correct
16 Correct 112 ms 9672 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Execution timed out 2131 ms 994700 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #4
0 / 19.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 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Execution timed out 2096 ms 333740 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 5.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 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Execution timed out 2096 ms 333740 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 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Execution timed out 2089 ms 336088 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 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Execution timed out 2089 ms 336088 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 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Execution timed out 2089 ms 336088 KB Time limit exceeded
4 Halted 0 ms 0 KB -