oj.uz

Submission #947577

# Submission time Handle Problem Language Result Execution time Memory
947577 2024-03-16T13:24:22 Z speedcode Awesome Arrowland Adventure (eJOI19_adventure) C++17
100 / 100
 55 ms 2204 KB 
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
const int INF = 1000000007;
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int m,n;
    cin >> m >> n;
    set<pair<int, pair<int, int>>> cache;
    char board[m][n];
    int distances[m][n];
    bool fixed[m][n];
    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++){
            cin >> board[i][j];
            distances[i][j] = INF;
            fixed[i][j] = 0;
        }
    }
    //Dijkstra !
    distances[0][0] = 0;
    cache.insert({0, {0,0}});

    while(cache.size()){
        auto k = *cache.begin();
        cache.erase(cache.begin());
        if(board[k.second.first][k.second.second] == 'X') {
            fixed[k.second.first][k.second.second] = 1;
            continue;
        }
        
        // E
        if(board[k.second.first][k.second.second] == 'E') {
            fixed[k.second.first][k.second.second] = 1;
            if(k.second.second < n-1 && !fixed[k.second.first][k.second.second+1] 
            && distances[k.second.first][k.second.second+1] > distances[k.second.first][k.second.second] + 0){
                cache.erase({distances[k.second.first][k.second.second+1], {k.second.first, k.second.second+1}});
                distances[k.second.first][k.second.second+1] = distances[k.second.first][k.second.second] + 0;
                cache.insert({distances[k.second.first][k.second.second+1], {k.second.first, k.second.second+1}});
            }
            // S
            if(k.second.first < m-1 && !fixed[k.second.first+1][k.second.second] 
            && distances[k.second.first+1][k.second.second] > distances[k.second.first][k.second.second] + 1){
                cache.erase({distances[k.second.first+1][k.second.second], {k.second.first+1, k.second.second}});
                distances[k.second.first+1][k.second.second] = distances[k.second.first][k.second.second] + 1;
                cache.insert({distances[k.second.first+1][k.second.second], {k.second.first+1, k.second.second}});
            }
            // W
            if(k.second.second > 0 && !fixed[k.second.first][k.second.second-1] 
            && distances[k.second.first][k.second.second-1] > distances[k.second.first][k.second.second] + 2){
                cache.erase({distances[k.second.first][k.second.second-1], {k.second.first, k.second.second-1}});
                distances[k.second.first][k.second.second-1] = distances[k.second.first][k.second.second] + 2;
                cache.insert({distances[k.second.first][k.second.second-1], {k.second.first, k.second.second-1}});
            }
            // N
            if(k.second.first > 0 && !fixed[k.second.first-1][k.second.second] 
            && distances[k.second.first-1][k.second.second] > distances[k.second.first][k.second.second] + 3){
                cache.erase({distances[k.second.first-1][k.second.second], {k.second.first-1, k.second.second}});
                distances[k.second.first-1][k.second.second] = distances[k.second.first][k.second.second] + 3;
                cache.insert({distances[k.second.first-1][k.second.second], {k.second.first-1, k.second.second}});
            }
            continue;
        }

        // S
        if(board[k.second.first][k.second.second] == 'S') {
            fixed[k.second.first][k.second.second] = 1;
            if(k.second.second < n-1 && !fixed[k.second.first][k.second.second+1] 
            && distances[k.second.first][k.second.second+1] > distances[k.second.first][k.second.second] + 3){
                cache.erase({distances[k.second.first][k.second.second+1], {k.second.first, k.second.second+1}});
                distances[k.second.first][k.second.second+1] = distances[k.second.first][k.second.second] + 3;
                cache.insert({distances[k.second.first][k.second.second+1], {k.second.first, k.second.second+1}});
            }
            // S
            if(k.second.first < m-1 && !fixed[k.second.first+1][k.second.second] 
            && distances[k.second.first+1][k.second.second] > distances[k.second.first][k.second.second] + 0){
                cache.erase({distances[k.second.first+1][k.second.second], {k.second.first+1, k.second.second}});
                distances[k.second.first+1][k.second.second] = distances[k.second.first][k.second.second] + 0;
                cache.insert({distances[k.second.first+1][k.second.second], {k.second.first+1, k.second.second}});
            }
            // W
            if(k.second.second > 0 && !fixed[k.second.first][k.second.second-1] 
            && distances[k.second.first][k.second.second-1] > distances[k.second.first][k.second.second] + 1){
                cache.erase({distances[k.second.first][k.second.second-1], {k.second.first, k.second.second-1}});
                distances[k.second.first][k.second.second-1] = distances[k.second.first][k.second.second] + 1;
                cache.insert({distances[k.second.first][k.second.second-1], {k.second.first, k.second.second-1}});
            }
            // N
            if(k.second.first > 0 && !fixed[k.second.first-1][k.second.second] 
            && distances[k.second.first-1][k.second.second] > distances[k.second.first][k.second.second] + 2){
                cache.erase({distances[k.second.first-1][k.second.second], {k.second.first-1, k.second.second}});
                distances[k.second.first-1][k.second.second] = distances[k.second.first][k.second.second] + 2;
                cache.insert({distances[k.second.first-1][k.second.second], {k.second.first-1, k.second.second}});
            }
            continue;
        }

        // W
        if(board[k.second.first][k.second.second] == 'W') {
            fixed[k.second.first][k.second.second] = 1;
            if(k.second.second < n-1 && !fixed[k.second.first][k.second.second+1] 
            && distances[k.second.first][k.second.second+1] > distances[k.second.first][k.second.second] + 2){
                cache.erase({distances[k.second.first][k.second.second+1], {k.second.first, k.second.second+1}});
                distances[k.second.first][k.second.second+1] = distances[k.second.first][k.second.second] + 2;
                cache.insert({distances[k.second.first][k.second.second+1], {k.second.first, k.second.second+1}});
            }
            // S
            if(k.second.first < m-1 && !fixed[k.second.first+1][k.second.second] 
            && distances[k.second.first+1][k.second.second] > distances[k.second.first][k.second.second] + 3){
                cache.erase({distances[k.second.first+1][k.second.second], {k.second.first+1, k.second.second}});
                distances[k.second.first+1][k.second.second] = distances[k.second.first][k.second.second] + 3;
                cache.insert({distances[k.second.first+1][k.second.second], {k.second.first+1, k.second.second}});
            }
            // W
            if(k.second.second > 0 && !fixed[k.second.first][k.second.second-1] 
            && distances[k.second.first][k.second.second-1] > distances[k.second.first][k.second.second] + 0){
                cache.erase({distances[k.second.first][k.second.second-1], {k.second.first, k.second.second-1}});
                distances[k.second.first][k.second.second-1] = distances[k.second.first][k.second.second] + 0;
                cache.insert({distances[k.second.first][k.second.second-1], {k.second.first, k.second.second-1}});
            }
            // N
            if(k.second.first > 0 && !fixed[k.second.first-1][k.second.second] 
            && distances[k.second.first-1][k.second.second] > distances[k.second.first][k.second.second] + 1){
                cache.erase({distances[k.second.first-1][k.second.second], {k.second.first-1, k.second.second}});
                distances[k.second.first-1][k.second.second] = distances[k.second.first][k.second.second] + 1;
                cache.insert({distances[k.second.first-1][k.second.second], {k.second.first-1, k.second.second}});
            }
            continue;
        }

        // N
        if(board[k.second.first][k.second.second] == 'N') {
            fixed[k.second.first][k.second.second] = 1;
            if(k.second.second < n-1 && !fixed[k.second.first][k.second.second+1] 
            && distances[k.second.first][k.second.second+1] > distances[k.second.first][k.second.second] + 1){
                cache.erase({distances[k.second.first][k.second.second+1], {k.second.first, k.second.second+1}});
                distances[k.second.first][k.second.second+1] = distances[k.second.first][k.second.second] + 1;
                cache.insert({distances[k.second.first][k.second.second+1], {k.second.first, k.second.second+1}});
            }
            // S
            if(k.second.first < m-1 && !fixed[k.second.first+1][k.second.second] 
            && distances[k.second.first+1][k.second.second] > distances[k.second.first][k.second.second] + 2){
                cache.erase({distances[k.second.first+1][k.second.second], {k.second.first+1, k.second.second}});
                distances[k.second.first+1][k.second.second] = distances[k.second.first][k.second.second] + 2;
                cache.insert({distances[k.second.first+1][k.second.second], {k.second.first+1, k.second.second}});
            }
            // W
            if(k.second.second > 0 && !fixed[k.second.first][k.second.second-1] 
            && distances[k.second.first][k.second.second-1] > distances[k.second.first][k.second.second] + 3){
                cache.erase({distances[k.second.first][k.second.second-1], {k.second.first, k.second.second-1}});
                distances[k.second.first][k.second.second-1] = distances[k.second.first][k.second.second] + 3;
                cache.insert({distances[k.second.first][k.second.second-1], {k.second.first, k.second.second-1}});
            }
            // N
            if(k.second.first > 0 && !fixed[k.second.first-1][k.second.second] 
            && distances[k.second.first-1][k.second.second] > distances[k.second.first][k.second.second] + 0){
                cache.erase({distances[k.second.first-1][k.second.second], {k.second.first-1, k.second.second}});
                distances[k.second.first-1][k.second.second] = distances[k.second.first][k.second.second] + 0;
                cache.insert({distances[k.second.first-1][k.second.second], {k.second.first-1, k.second.second}});
            }
            continue;
        }
    }

    cout << (distances[m-1][n-1] == INF ? -1 : distances[m-1][n-1]) << '\n';
    
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 456 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 388 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct

Subtask #5
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 456 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 344 KB Output is correct
26 Correct 0 ms 388 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 1 ms 460 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 1 ms 344 KB Output is correct
35 Correct 5 ms 600 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 5 ms 604 KB Output is correct
38 Correct 1 ms 604 KB Output is correct
39 Correct 53 ms 2204 KB Output is correct
40 Correct 52 ms 2140 KB Output is correct
41 Correct 3 ms 2140 KB Output is correct
42 Correct 52 ms 2200 KB Output is correct
43 Correct 55 ms 2136 KB Output is correct
44 Correct 3 ms 2136 KB Output is correct