Submission #288530

#	Time	Username	Problem	Language	Result	Execution time	Memory
288530		FulopMate	Awesome Arrowland Adventure (eJOI19_adventure)	C++14	100 / 100	192 ms	31276 KiB

adventure

#include <bits/stdc++.h>

using namespace std;
vector<int> g[250000], s[250000];
char mp[500][500];
int tav[250000];

unordered_map<char, array<int, 4>> dirtos = {
    {'E', {0, 1, 2, 3}},
    {'S', {3, 0, 1, 2}},
    {'W', {2, 3, 0, 1}},
    {'N', {1, 2, 3, 0}}
};

int main(){
    int n, m; cin>>n>>m;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            char c; cin>>c;
            mp[i][j] = c;
            if(c=='X')continue;
            int nodeindex = i*500+j;
            if(j < m-1 && mp[i][j+1] != 'X'){
                g[nodeindex].push_back(nodeindex+1);
                s[nodeindex].push_back(dirtos[c][0]);
            }
            if(i < n-1 && mp[i+1][j] != 'X'){
                g[nodeindex].push_back(nodeindex+500);
                s[nodeindex].push_back(dirtos[c][1]);
            }
            if(j > 0 && mp[i][j-1] != 'X'){
                g[nodeindex].push_back(nodeindex-1);
                s[nodeindex].push_back(dirtos[c][2]);
            }
            if(i > 0 && mp[i-1][j] != 'X'){
                g[nodeindex].push_back(nodeindex-500);
                s[nodeindex].push_back(dirtos[c][3]);
            }
        }
    }
    priority_queue<pair<int,int>> q;
    for(int&i:tav)i=INT_MAX;
    tav[0] = 0;
    q.push({0, 0});
    while(!q.empty()){
        int v = q.top().second;
        int t = -q.top().first;
        q.pop();
        if(tav[v] < t)continue;
        for(int i = 0; i < g[v].size(); i++){
            int k = g[v][i];
            int su = s[v][i];
            if(t + su < tav[k]){
                tav[k] = t+su;
                q.push({-tav[k], k});
            }
        }
    }
    if(tav[(n-1)*500+(m-1)] == INT_MAX)cout<<-1;
    else cout<<tav[(n-1)*500+(m-1)];
    return 0;
}

Compilation message (stderr)

adventure.cpp: In function 'int main()':
adventure.cpp:50:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         for(int i = 0; i < g[v].size(); i++){
      |                        ~~^~~~~~~~~~~~~

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