oj.uz

Submission #826425

# Submission time Handle Problem Language Result Execution time Memory
826425 2023-08-15T14:44:49 Z brotherDemonInHell Awesome Arrowland Adventure (eJOI19_adventure) C++17
100 / 100
 116 ms 8940 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
using ll = long long;
using ld = long double;

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
gp_hash_table<ll, ll, custom_hash> app;
//const int MOD = 998244353;
//const int MOD = 1e9 + 7;

const ll INF = 3e18;

vector<string> a;


ll n, m, k, q, x, y, z, w, h, T;
string s, t;
double p;

char conv(ll delx, ll dely) {
    if (delx == 1) {
        return 'S';
    }
    if (delx == -1) {
        return 'N';
    }
    if (dely == 1) {
        return 'E';
    }
    return 'W';
}

ll distan(char c1, char c2) {
    vector<ll> here;
    for (char c : {c1, c2}) {
        if (c == 'N') here.push_back(0);
        else if (c == 'E') here.push_back(1);
        else if (c == 'S') here.push_back(2);
        else here.push_back(3);
    }
    return (here[1] - here[0] + 4) % 4;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    T = 1;
    //cin >> T;
    while (T--) {    
        cin >> n >> m;
        a.assign(n, "");
        for (int i = 0; i <  n; i++) {
            cin >> a[i];
        }
        priority_queue<pair<ll, pair<ll, ll>>, vector<pair<ll, pair<ll, ll>>>, greater<pair<ll, pair<ll, ll>>>> pq;
        vector<vector<bool>> vis(n, vector<bool>(m));
        vector<vector<ll>> dist(n, vector<ll>(m, INF));
        dist[0][0] = 0;
        pq.push({0, {0, 0}});
        ll ans = -1;
        while (!pq.empty()) {
            pair<ll, pair<ll, ll>> top = pq.top();
            pq.pop();
            x = top.second.first;
            y = top.second.second;
            if (x == n - 1 && y == m - 1) {
                ans = top.first;
                break;
            }
            if (vis[x][y] || a[x][y] == 'X') continue;
            vis[x][y] = true;

            for (ll delx : {-1, 1}) {
                ll dely = 0;
                if (delx + x < 0 || delx + x >= n || dely + y < 0 || dely + y >= m 
                || ((delx + x != n - 1 || dely + y != m - 1) && a[delx + x][dely + y] == 'X')) continue;
                ll here = distan(a[x][y], conv(delx, dely));
                if (dist[x][y] + here < dist[x + delx][y + dely]) {
                    dist[x + delx][y + dely] = dist[x][y] + here;
                    pq.push({dist[x + delx][y + dely], {x + delx, y + dely}});
                }
            }
            for (ll dely : {-1, 1}) {
                ll delx = 0;
                if (delx + x < 0 || delx + x >= n || dely + y < 0 || dely + y >= m 
                || ((delx + x != n - 1 || dely + y != m - 1) && a[delx + x][dely + y] == 'X')) continue;
                ll here = distan(a[x][y], conv(delx, dely));
                if (dist[x][y] + here < dist[x + delx][y + dely]) {
                    dist[x + delx][y + dely] = dist[x][y] + here;
                    pq.push({dist[x + delx][y + dely], {x + delx, y + dely}});
                }
            }
        }

        printf("%lld\n", ans);
    }


}

Subtask #1
10.0 / 10.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct

Subtask #4
16.0 / 16.0

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

Subtask #5
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 0 ms 212 KB Output is correct
26 Correct 0 ms 212 KB Output is correct
27 Correct 0 ms 212 KB Output is correct
28 Correct 1 ms 212 KB Output is correct
29 Correct 1 ms 212 KB Output is correct
30 Correct 0 ms 212 KB Output is correct
31 Correct 0 ms 212 KB Output is correct
32 Correct 0 ms 212 KB Output is correct
33 Correct 0 ms 212 KB Output is correct
34 Correct 1 ms 212 KB Output is correct
35 Correct 7 ms 536 KB Output is correct
36 Correct 0 ms 340 KB Output is correct
37 Correct 7 ms 592 KB Output is correct
38 Correct 1 ms 724 KB Output is correct
39 Correct 71 ms 2692 KB Output is correct
40 Correct 75 ms 2656 KB Output is correct
41 Correct 2 ms 2516 KB Output is correct
42 Correct 70 ms 2668 KB Output is correct
43 Correct 116 ms 8940 KB Output is correct
44 Correct 1 ms 2516 KB Output is correct