Submission #1106099

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106099		nasir_bashirov	Awesome Arrowland Adventure (eJOI19_adventure)	C++11	100 / 100	68 ms	6596 KiB

adventure

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,fma")

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define vll vector<pll>
#define all(x)    x.begin(), x.end()
#define fastio\
    ios_base::sync_with_stdio(0);\
    cin.tie(0);\
    cout.tie(0)\

const int sz = 505;
const int inf = 1e9 + 7;
int w[4][4] = {{0, 2, 1, 3}, {2, 0, 3, 1}, {3, 1, 0, 2}, {1, 3, 2, 0}};
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, 1, -1};
ll d[sz][sz], n, m;
char adj[sz][sz];

void djikstra(){
    map<int, char> ind;
    priority_queue<pair<int, pii>, vector<pair<int, pii>>, greater<pair<int, pii>>> pq;
    pq.push({0, {1, 1}});
    d[1][1] = 0;
    ind['N'] = 0, ind['S'] = 1, ind['E'] = 2, ind['W'] = 3;
    while(!pq.empty()){
        int x = pq.top().second.first, y = pq.top().second.second;
        pq.pop();
        for(int i = 0; i < 4; i++){
            int xx = x + dx[i], yy = y + dy[i];
            char c = adj[x][y];
            if(c == 'X')    break;
            if(d[xx][yy] > d[x][y] + w[ind[c]][i]){
                d[xx][yy] = d[x][y] + w[ind[c]][i];
                pq.push({d[xx][yy], {xx, yy}});
            }
        }
    }
}

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> adj[i][j];
            d[i][j] = inf;
        }
    }
    djikstra();
    if(d[n][m] == inf)  cout << -1;
    else    cout << d[n][m];
}

Compilation message (stderr)

adventure.cpp: In function 'void djikstra()':
adventure.cpp:42:46: warning: array subscript has type 'char' [-Wchar-subscripts]
   42 |             if(d[xx][yy] > d[x][y] + w[ind[c]][i]){
      |                                              ^
adventure.cpp:43:47: warning: array subscript has type 'char' [-Wchar-subscripts]
   43 |                 d[xx][yy] = d[x][y] + w[ind[c]][i];
      |                                               ^

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 16 / 16
• Subtask 5: 50 / 50