oj.uz

Submission #840850

# Submission time Handle Problem Language Result Execution time Memory
840850 2023-08-31T18:44:24 Z raul2008487 Awesome Arrowland Adventure (eJOI19_adventure) C++17
100 / 100
 56 ms 18252 KB 
#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

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 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 1 ms 340 KB Output is correct
7 Correct 1 ms 212 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 340 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 0 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 1 ms 340 KB Output is correct
7 Correct 1 ms 212 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 340 KB Output is correct
11 Correct 0 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 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 0 ms 212 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 1 ms 340 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 340 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 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 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #5
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 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 1 ms 340 KB Output is correct
7 Correct 1 ms 212 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 340 KB Output is correct
11 Correct 0 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 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 0 ms 212 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 1 ms 340 KB Output is correct
23 Correct 0 ms 332 KB Output is correct
24 Correct 0 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 0 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 0 ms 340 KB Output is correct
33 Correct 0 ms 340 KB Output is correct
34 Correct 1 ms 340 KB Output is correct
35 Correct 4 ms 720 KB Output is correct
36 Correct 0 ms 340 KB Output is correct
37 Correct 4 ms 724 KB Output is correct
38 Correct 1 ms 1364 KB Output is correct
39 Correct 41 ms 3148 KB Output is correct
40 Correct 37 ms 2832 KB Output is correct
41 Correct 3 ms 2772 KB Output is correct
42 Correct 37 ms 2772 KB Output is correct
43 Correct 56 ms 18252 KB Output is correct
44 Correct 3 ms 2772 KB Output is correct