Submission #840850

#	Time	Username	Problem	Language	Result	Execution time	Memory
840850		raul2008487	Awesome Arrowland Adventure (eJOI19_adventure)	C++17	100 / 100	56 ms	18252 KiB

adventure

#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define in insert
#define ld long double
#define ll long long
#define pii pair<ll,ll>
#define vl vector<ll>
#define mpr make_pair
#define F first
#define S second
#define lg(a) __lg(a)
#define all(v) v.begin(),v.end()
//#define endl "\n"
#define inf 0x3F3F3F3F
using namespace std;
const int mod = 1e9+7;
const int sz = 3e5+5;
const ll oo = 1000000000000000005;
/*struct BIT {
    vector<int> bit;  // binary indexed tree
    int n;

    BIT(int n) {
        this->n = n;
        bit.assign(n, 0);
    }

    /*BIT(vector<int> const &a) : BIT(a.size()) {
        for (size_t i = 0; i < a.size(); i++)
            add(i, a[i]);
    }
    BIT(vector<ll> const &a) : BIT(a.size()){
        for(size_t i=0;i<a.size();i++){
            add(i,a[i]);
        }
    }
    int sum(int r) {
        int ret = 0;
        for (; r >= 0; r = (r & (r + 1)) - 1)
            ret += bit[r];
        return ret;
    }

    int sum(int l, int r) {
        return sum(r) - sum(l - 1);
    }

    void add(int idx, int delta) {
        for (; idx < n; idx = idx | (idx + 1))
            bit[idx] += delta;
    }
};*/

set<pair<ll,pair<ll,ll>>> s;
ll dis[505][505];
ll dif[27][27];
void init(ll n, ll m){
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=m;j++){
            dis[i][j] = inf;
        }
    }
    dis[1][1]=0;
}
void solve(){
    ll n,m,i,j;
    cin>>n>>m;
    init(n,m);
    char a[n+1][m+1];
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            cin>>a[i][j];
        }
    }
    if(a[1][1] == 'X'){
        cout << -1 << endl;
        return ;
    }
    a[n][m]='E';
    dif['N' - 'A']['N' - 'A'] = 0;dif['N' - 'A']['E' - 'A'] = 1;dif['N' - 'A']['S' - 'A'] = 2;dif['N' - 'A']['W' - 'A'] = 3;
    dif['E' - 'A']['N' - 'A'] = 3;dif['E' - 'A']['E' - 'A'] = 0;dif['E' - 'A']['S' - 'A'] = 1;dif['E' - 'A']['W' - 'A'] = 2;
    dif['S' - 'A']['N' - 'A'] = 2;dif['S' - 'A']['E' - 'A'] = 3;dif['S' - 'A']['S' - 'A'] = 0;dif['S' - 'A']['W' - 'A'] = 1;
    dif['W' - 'A']['N' - 'A'] = 1;dif['W' - 'A']['E' - 'A'] = 2;dif['W' - 'A']['S' - 'A'] = 3;dif['W' - 'A']['W' - 'A'] = 0;


    s.in({0,{1,1}});
    while(!s.empty()){
        auto st = s.begin();
        ll d_to_v = (st -> first);
        pair<ll,ll> from = (st -> second);
        ll x = from.first;
        ll y = from.second;
        s.erase(st);
        if(x==n && y==m){break;}
        if(dis[x][y] != d_to_v){
            continue;
        }
        if(from.first < n && a[x+1][y] != 'X'){
            if(dis[x+1][y] > dis[x][y] + dif[a[x][y]-'A']['S'-'A']){
                dis[x+1][y] = dis[x][y] + dif[a[x][y]-'A']['S'-'A'];
                s.in({dis[x+1][y],{x+1,y}});
            }
        }
        if(from.first > 1 && a[x-1][y] != 'X'){
            if(dis[x-1][y] > dis[x][y] + dif[a[x][y]-'A']['N'-'A']){
                dis[x-1][y] = dis[x][y] + dif[a[x][y]-'A']['N'-'A'];
                s.in({dis[x-1][y],{x-1,y}});
            }
        }
        if(from.second < m && a[x][y+1] != 'X'){
            if(dis[x][y+1] > dis[x][y] + dif[a[x][y]-'A']['E'-'A']){
                dis[x][y+1] = dis[x][y] + dif[a[x][y]-'A']['E'-'A'];
                s.in({dis[x][y+1],{x,y+1}});
            }
        }
        if(from.second > 1 && a[x][y-1] != 'X'){
            if(dis[x][y-1] > dis[x][y] + dif[a[x][y]-'A']['W'-'A']){
                dis[x][y-1] = dis[x][y] + dif[a[x][y]-'A']['W'-'A'];
                s.in({dis[x][y-1],{x,y-1}});
            }
        }
    }
    if(dis[n][m] == inf){
        cout << -1 << endl;
        return ;
    }
    cout << dis[n][m] << endl;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll t=1;
    //cin>>t;
    while(t--){
        solve();
    }

}
/*
2 1
1 2 5
4
2
1 2
*/

Compilation message (stderr)

adventure.cpp:29:5: warning: "/*" within comment [-Wcomment]
   29 |     /*BIT(vector<int> const &a) : BIT(a.size()) {
      |

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