oj.uz

Submission #244265

# Submission time Handle Problem Language Result Execution time Memory
244265 2020-07-03T12:45:31 Z Matteo_Verz Awesome Arrowland Adventure (eJOI19_adventure) C++11
34 / 100
 5 ms 640 KB 
/*
                `-/oo+/-   ``
              .oyhhhhhhyo.`od
             +hhhhyyoooos. h/
            +hhyso++oosy- /s
           .yoooossyyo:``-y`
            ..----.` ``.-/+:.`
                   `````..-::/.
                  `..```.-::///`
                 `-.....--::::/:
                `.......--::////:
               `...`....---:::://:
             `......``..--:::::///:`
            `---.......--:::::////+/`
            ----------::::::/::///++:
            ----:---:::::///////////:`
            .----::::::////////////:-`
            `----::::::::::/::::::::-
             `.-----:::::::::::::::-
               ...----:::::::::/:-`
                 `.---::/+osss+:`
                   ``.:://///-.
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cmath>

using namespace std;

const int INF = 2e9;
const int N = 500;

int n, m;

vector <pair <int, int>> g[5 + N];
bool viz[5 + N * N];
int dp[5 + N * N];

priority_queue <pair <int, int>, vector <pair <int, int>>, greater <pair <int, int>>> heap;

void Dijkstra(int nodStart) {
    for(int i = 1; i <= n * m; i++) dp[i] = INF;

    dp[nodStart] = 0;
    heap.push(make_pair(0, nodStart));

    while(heap.size()) {
        pair <int, int> top = heap.top();
        heap.pop();

        if(viz[top.second] == false) {
            viz[top.second] = true;

            for(auto to : g[top.second]) {
                if(dp[to.second] > to.first + dp[top.second]) {
                    dp[to.second] = to.first + dp[top.second];
                    heap.push(make_pair(dp[to.second], to.second));
                }
            }
        }
    }
}

int main() {
#ifdef BLAT
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
#endif // BLAT

    cin >> n >> m;

    for(int i = 1; i <= n; i++) {
        string s;
        cin >> s;

        for(int j = 0; j < s.size(); j++) {
            int idx = (i - 1) * m + j + 1;
            int idxn, idxe, idxs, idxw;
            idxn = idx - m;
            idxs = idx + m;
            idxe = idx + 1;
            idxw = idx - 1;

            if(s[j] == 'N') {
                if(i > 1) g[idx].push_back(make_pair(0, idxn));
                if(j < m - 1) g[idx].push_back(make_pair(1, idxe));
                if(i < n) g[idx].push_back(make_pair(2, idxs));
                if(j > 0) g[idx].push_back(make_pair(3, idxw));
            } else if(s[j] == 'E') {
                if(i > 1) g[idx].push_back(make_pair(3, idxn));
                if(j < m - 1) g[idx].push_back(make_pair(0, idxe));
                if(i < n) g[idx].push_back(make_pair(1, idxs));
                if(j > 0) g[idx].push_back(make_pair(2, idxw));
            } else if(s[j] == 'S') {
                if(i > 1) g[idx].push_back(make_pair(2, idxn));
                if(j < m - 1) g[idx].push_back(make_pair(3, idxe));
                if(i < n) g[idx].push_back(make_pair(0, idxs));
                if(j > 0) g[idx].push_back(make_pair(1, idxw));
            } else if(s[j] == 'W') {
                if(i > 1) g[idx].push_back(make_pair(1, idxn));
                if(j < m - 1) g[idx].push_back(make_pair(2, idxe));
                if(i < n) g[idx].push_back(make_pair(3, idxs));
                if(j > 0) g[idx].push_back(make_pair(0, idxw));
            }
        }
    }

    Dijkstra(1);

    if(dp[n * m] == INF) cout << -1 << '\n';
    else cout << dp[n * m] << '\n';
    return 0;
}

Compilation message

adventure.cpp: In function 'int main()':
adventure.cpp:84:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < s.size(); j++) {
                        ~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 640 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 4 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 4 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 4 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 4 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 4 ms 384 KB Output is correct
22 Correct 4 ms 384 KB Output is correct
23 Correct 4 ms 384 KB Output is correct
24 Correct 5 ms 384 KB Output is correct
25 Runtime error 5 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Halted 0 ms 0 KB -