oj.uz

Submission #882581

# Submission time Handle Problem Language Result Execution time Memory
882581 2023-12-03T11:59:02 Z db_123 Awesome Arrowland Adventure (eJOI19_adventure) C++14
38 / 100
 1 ms 604 KB 
#include <iostream>
#include <vector>
#include <set>

using namespace std;

struct Info {
    int node;
    int cost;
    Info() = default;
    Info(int node, int cost) {
        this->node = node;
        this->cost = cost;
    }
    bool operator<(Info a2) const {
        if(cost == a2.cost) {
            return node<a2.node;
        }
        return cost<a2.cost;
    }
};

int n,m;
vector<vector<char>> ma;
vector<vector<Info>> graph;

void read() {
    cin>>n>>m;
    ma.resize(n+1, vector<char>(m+1));
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            cin>>ma[i][j];
        }
    }
}

void form_graph() {
    graph.resize(n*m+1);
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            vector<int> delta;
            if(ma[i][j] == 'N') {
                delta = {0, 1, 2, 3};
            }
            else if(ma[i][j] == 'E') {
                delta = {3, 0, 1, 2};
            }
            else if(ma[i][j] == 'S') {
                delta = {2, 3, 0, 1};
            }
            else {
                delta = {1, 2, 3, 0};
            }
            int curr_node = (i-1)*m + j;
            int node_dr = (i-1)*m + j + 1;
            int node_st = (i-1)*m + j - 1;
            int node_jos = i * m + j;
            int node_sus = (i-2)*m + j;
            if(i-1>0 && ma[i-1][j]!='X') {
                graph[curr_node].push_back(*new Info(node_sus, delta[0]));
            }
            if(j+1<=m && ((i==n && j==m-1) || ma[i][j+1]!='X')) {
                graph[curr_node].push_back(*new Info(node_dr, delta[1]));
            }
            if(i+1<=n && ((i==n-1 && j==m) || ma[i+1][j+1]!='X')) {
                graph[curr_node].push_back(*new Info(node_jos, delta[2]));
            }
            if(j-1>0 && ma[i][j-1]!='X') {
                graph[curr_node].push_back(*new Info(node_st, delta[3]));
            }
        }
    }
}

int dijkstra() {
    vector<int> dist(n*m+1, 1e9);
    set<Info> st;
    st.insert(*new Info(1, 0));
    dist[1] = 0;
    Info tp;
    while(!st.empty()) {
        tp = (*st.begin());
        st.erase(st.begin());
        for(auto it : graph[tp.node]) {
            if(dist[it.node] > dist[tp.node] + it.cost) {
                dist[it.node] = dist[tp.node] + it.cost;
                st.insert(*new Info(it.node, dist[it.node]));
            }
        }
    }
    if(dist[n*m]==1e9) {
        dist[n*m]=-1;
    }
    return dist[n*m];
}

void solve() {
    form_graph();
    cout<<dijkstra();
}

int main() {

    read();
    solve();
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
0 / 12.0

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

Subtask #4
16.0 / 16.0

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

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 436 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 1 ms 408 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 344 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Incorrect 0 ms 348 KB Output isn't correct
25 Halted 0 ms 0 KB -