oj.uz

Submission #972901

# Submission time Handle Problem Language Result Execution time Memory
972901 2024-05-01T10:02:16 Z vjudge1 Awesome Arrowland Adventure (eJOI19_adventure) C++17
100 / 100
 76 ms 5832 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int INF = 1e8;
const int N = 505;
vector<vector<int>>dist(N, vector<int>(N, INF));
char grid[N][N];
map<char, int>mp;

int dx(int c){
    if(c%4 == 0) return -1;
    if(c%4 == 2) return 1;
    return 0;
}

int dy(int c){
    if(c%4 == 1) return 1;
    if(c%4 == 3) return -1;
    return 0;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    mp['N'] = 0; mp['E'] = 1; mp['S'] = 2; mp['W'] = 3;
    int R, C; cin >> R >> C;

    for(int i = 1; i <= R; i++){
        for(int j = 1; j <= C; j++)
            cin >> grid[i][j];
    }  

    dist[1][1] = 0;
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>>q; q.emplace(0, 1, 1);

    const auto ok = [&](int x, int y) -> bool {
        return (1 <= x && x <= R && 1 <= y && y <= C);
    };

    while(!q.empty()){
        auto [d, x, y] = q.top(); q.pop();
        if(grid[x][y] == 'X') continue;
        if(d > dist[x][y]) continue;

        for(int i = 0; i <= 3; i++){
            int nx = x + dx(mp[grid[x][y]] + i);
            int ny = y + dy(mp[grid[x][y]] + i);

            if(ok(nx, ny) && dist[nx][ny] > dist[x][y] + i){
                dist[nx][ny] = dist[x][y] + i;
                q.emplace(dist[nx][ny], nx, ny);
            }
        }
    }

    if(dist[R][C] == INF) dist[R][C] = -1;
    cout << dist[R][C] << '\n';

    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1368 KB Output is correct
2 Correct 1 ms 1372 KB Output is correct
3 Correct 1 ms 1372 KB Output is correct
4 Correct 1 ms 1348 KB Output is correct
5 Correct 1 ms 1372 KB Output is correct
6 Correct 1 ms 1372 KB Output is correct
7 Correct 1 ms 1372 KB Output is correct
8 Correct 1 ms 1368 KB Output is correct
9 Correct 1 ms 1388 KB Output is correct
10 Correct 1 ms 1372 KB Output is correct

Subtask #5
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1372 KB Output is correct
2 Correct 1 ms 1372 KB Output is correct
3 Correct 1 ms 1368 KB Output is correct
4 Correct 1 ms 1372 KB Output is correct
5 Correct 1 ms 1372 KB Output is correct
6 Correct 1 ms 1372 KB Output is correct
7 Correct 1 ms 1372 KB Output is correct
8 Correct 1 ms 1372 KB Output is correct
9 Correct 1 ms 1484 KB Output is correct
10 Correct 1 ms 1372 KB Output is correct
11 Correct 1 ms 1372 KB Output is correct
12 Correct 1 ms 1372 KB Output is correct
13 Correct 1 ms 1372 KB Output is correct
14 Correct 1 ms 1484 KB Output is correct
15 Correct 1 ms 1372 KB Output is correct
16 Correct 1 ms 1372 KB Output is correct
17 Correct 1 ms 1368 KB Output is correct
18 Correct 1 ms 1372 KB Output is correct
19 Correct 1 ms 1476 KB Output is correct
20 Correct 1 ms 1368 KB Output is correct
21 Correct 1 ms 1372 KB Output is correct
22 Correct 1 ms 1372 KB Output is correct
23 Correct 1 ms 1368 KB Output is correct
24 Correct 1 ms 1372 KB Output is correct
25 Correct 1 ms 1368 KB Output is correct
26 Correct 1 ms 1372 KB Output is correct
27 Correct 1 ms 1372 KB Output is correct
28 Correct 1 ms 1348 KB Output is correct
29 Correct 1 ms 1372 KB Output is correct
30 Correct 1 ms 1372 KB Output is correct
31 Correct 1 ms 1372 KB Output is correct
32 Correct 1 ms 1368 KB Output is correct
33 Correct 1 ms 1388 KB Output is correct
34 Correct 1 ms 1372 KB Output is correct
35 Correct 5 ms 1368 KB Output is correct
36 Correct 1 ms 1372 KB Output is correct
37 Correct 6 ms 1496 KB Output is correct
38 Correct 2 ms 1628 KB Output is correct
39 Correct 53 ms 2016 KB Output is correct
40 Correct 54 ms 1880 KB Output is correct
41 Correct 4 ms 1884 KB Output is correct
42 Correct 50 ms 1880 KB Output is correct
43 Correct 76 ms 5832 KB Output is correct
44 Correct 3 ms 1880 KB Output is correct