oj.uz

Submission #530982

# Submission time Handle Problem Language Result Execution time Memory
530982 2022-02-27T09:02:18 Z Servus2022 Awesome Arrowland Adventure (eJOI19_adventure) C++14
0 / 100
 4 ms 6240 KB 
#include <iostream>
#include <vector>
#include <queue>

using namespace std;
typedef pair <int, int> PII;

const int NMAX = 502, INF = 1e9;

const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};


char v[NMAX][NMAX];
int d[NMAX * NMAX], sel[NMAX * NMAX];
int N, M;

vector < PII > G[NMAX * NMAX];

auto cmp = [](PII a, PII b)
{
    if(!(a.first < b.first))
        return 1;
    return 0;
};

priority_queue <PII, vector <PII>, decltype(cmp)> H(cmp);

inline int code(PII a)
{
    if(!(1 <= a.first && a.first <= N && 1 <= a.second && a.second <= M))
        return 0;
    if(v[a.first][a.second] == 'X' && (a.first != N || a.second != M))
        return 0;
    return (a.first - 1) * M + a.second;
}

inline PII decode(int x)
{
    if(x % M == 0)
        return {x / M, M};
    return {x / M, x % M};
}

inline void Read()
{
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);

    cin >> N >> M;
    for(int i = 1; i <= N; ++i)
    {
        cin >> (v[i] + 1);
        for(int j = 1; j <= M; ++j)
        {
            if(v[i][j] == 'X' && (i != N || j != M))
                continue;

            PII est = {i, j + 1}, west = {i, j - 1}, sud = {i + 1, j}, nord = {i - 1, j};
            int ct = code({i, j});
            if(v[i][j] == 'E')
            {
                G[ct].push_back({0, code (est)});
                G[ct].push_back({1, code (sud)});
                G[ct].push_back({2, code (west)});
                G[ct].push_back({3, code (nord)});
            }
            if(v[i][j] == 'S')
            {
                G[ct].push_back({0, code (sud)});
                G[ct].push_back({1, code (west)});
                G[ct].push_back({2, code (nord)});
                G[ct].push_back({3, code (est)});
            }
            if(v[i][j] == 'W')
            {
                G[ct].push_back({0, code (west)});
                G[ct].push_back({1, code (nord)});
                G[ct].push_back({2, code (est)});
                G[ct].push_back({3, code (sud)});
            }
            if(v[i][j] == 'N')
            {
                G[ct].push_back({0, code (nord)});
                G[ct].push_back({1, code (est)});
                G[ct].push_back({2, code (sud)});
                G[ct].push_back({3, code (west)});
            }
        }
    }
    return;
}

inline void Dijkstra(int start)
{
    for(int i = 1; i <= code({N, M}); ++i)
        d[i] = INF;

    for(auto it: G[start])
        if(it.second)
            H.push(it), d[it.second] = it.first;

    d[start] = 0;
    sel[start] = 1;

    while(!H.empty())
    {
        while(!H.empty() && sel[H.top().second])
            H.pop();
        if(H.empty())
            return;

        int node = H.top().second;
        sel[node] = 1;
        H.pop();

        for(auto it: G[node])
            if(it.second)
                if(d[node] + it.first < d[it.second])
                    d[it.second] = d[node] + it.first, H.push({d[it.second], it.second});
    }
    return;
}

int main()
{
    Read();
    Dijkstra(1);
    cout << d[code({N, M})] << '\n';
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 6220 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 6220 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6240 KB Output is correct
2 Correct 3 ms 6220 KB Output is correct
3 Incorrect 3 ms 6220 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 6220 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 6220 KB Output isn't correct
2 Halted 0 ms 0 KB -