oj.uz

Submission #543654

# Submission time Handle Problem Language Result Execution time Memory
543654 2022-03-31T07:47:03 Z tudor Awesome Arrowland Adventure (eJOI19_adventure) C++17
34 / 100
 1 ms 340 KB 
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int nmax = 500;
const int dir = 4;
const int inf = 1e9;
int n, m;
char a[nmax + 2][nmax + 2];
int dl[dir] = { -1, 0, 1,  0 };
int dc[dir] = {  0, 1, 0, -1 };
int cod[128];
int dist[nmax * nmax + 1];
int vis[nmax * nmax + 1];
vector < pair < int, int > > g[nmax + 1];
void dijkstra ( int start ) {
    priority_queue < pair < int, int > > pq;
    for ( int i = 0; i < n * m; i++ )
        dist[i] = inf;
    dist[0] = 0;
    pq.push ( { 0, start } );
    while ( ! pq.empty() ) {
        int node = pq.top ().second;
        pq.pop ();
        if ( vis[node] == false ) {
            vis[node] = true;
            for ( auto x: g[node] )
                if ( dist[node] + x.second < dist[x.first] ) {
                    dist[x.first] = dist[node] + x.second;
                    pq.push ( { -dist[x.first], x.first } );
                }
        }
    }
}

static inline void add ( int x, int y, int d ) {
    if ( 0 <= x && x < n * m && 0 <= y && y < n * m )
        g[x].push_back ( { y, d } );
}
static inline int lin ( int x, int y ) {
    if ( x < 0 || x >= n || y < 0 || y >= m )
        return -1;
    return x * m + y;
}
int vec[4];
int main () {
    cin >> n >> m;
    for ( int i = 0; i < n; i++ )
        cin >> a[i];
    cod['N'] = 0; cod['E'] = 1; cod['S'] = 2; cod['W'] = 3;
    cod['X'] = -1;
    for ( int i = 0; i < n; i++ )
        for ( int j = 0; j < m; j++ )
            if ( a[i][j] != 'X' ) {
                int curr = lin ( i, j ), x;
                for ( int d = 0; d < dir; d++ )
                    vec[d] = lin ( i + dl[d], j + dc[d] );
                for ( int k = 0; k < 4; k++ )
                    if ( ( x = vec[( cod[a[i][j]] + k ) % dir] ) != -1 )
                        add ( curr, x , k );
            }
    dijkstra ( 0 );
    int r = dist[lin ( n - 1, m - 1 )];
    cout << ( r == inf? -1 : r );

    return 0;
}

Compilation message

adventure.cpp: In function 'int main()':
adventure.cpp:59:48: warning: array subscript has type 'char' [-Wchar-subscripts]
   59 |                     if ( ( x = vec[( cod[a[i][j]] + k ) % dir] ) != -1 )
      |                                          ~~~~~~^

Subtask #1
10.0 / 10.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 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

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 328 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 316 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 320 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 0 ms 212 KB Output is correct
27 Correct 1 ms 324 KB Output is correct
28 Correct 1 ms 324 KB Output is correct
29 Incorrect 1 ms 340 KB Output isn't correct
30 Halted 0 ms 0 KB -