oj.uz

답안 #244262

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
244262 2020-07-03T12:39:07 Z Matteo_Verz Awesome Arrowland Adventure (eJOI19_adventure) C++11
34 / 100
 5 ms 512 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];

class Min_Heap {
    private:
        pair <int, int> h[5 + N * 8];
        int sz;

        void Sift_Up(int pos) {
            int parent;
            parent = pos >> 1;

            while(h[pos].second < h[parent].second && parent > 0) {
                swap(h[pos], h[parent]);

                pos = parent;
                parent = pos >> 1;
            }
        }

        void Sift_Down(int pos) {
            int child;
            child = pos << 1;

            if(child + 1 <= sz && h[child].second > h[child + 1].second)
                child++;
            while(child <= sz && h[child].second < h[pos].second) {
                swap(h[pos], h[child]);

                pos = child;
                child = pos << 1;

                if(child + 1 <= sz && h[child].second > h[child + 1].second) child++;
            }
        }

    public:
        void Clear() {
            sz = 0;
        }

        void Push(pair <int, int> val) {
            h[++sz] = val;
            Sift_Up(sz);
        }

        void Pop() {
            swap(h[1], h[sz]);
            sz--;
            Sift_Down(1);
        }

        pair <int, int> Top() {
            return h[1];
        }

        int Size() {
            return sz;
        }
};
Min_Heap heap;

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

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

    while(heap.Size()) {
        pair <int, int> top = heap.Top();
        heap.Pop();

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

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

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

    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:141: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

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 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

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 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 5 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 416 KB Output is correct
16 Correct 5 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 5 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct

Subtask #4
0 / 16.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 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 5 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 416 KB Output is correct
16 Correct 5 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 5 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 5 ms 384 KB Output is correct
23 Correct 5 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 -