oj.uz

Submission #1118583

# Submission time Handle Problem Language Result Execution time Memory
1118583 2024-11-25T17:24:25 Z heey Awesome Arrowland Adventure (eJOI19_adventure) C++14
50 / 100
 2000 ms 19016 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
int h[200005];
struct g{int x, y, t;};

int df(char cur, char dir){
    if(cur == dir) return 0;
    if(cur == 'N') return 1 + df('E', dir);
    if(cur == 'E') return 1 + df('S', dir);
    if(cur == 'S') return 1 + df('W', dir);
    if(cur == 'W') return 1 + df('N', dir);
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, m; cin >> n >> m;
    vector<vector<char>> a(n, vector<char>(m));

    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> a[i][j];
        }
    }


    vector<vector<int>> t(n, vector<int>(m, INT_MAX));
    queue<g> bfs;
    bfs.push({0, 0, 0});
    while(!bfs.empty()){
        g cur = bfs.front();
        bfs.pop();
        if(cur.x >= 0 && cur.x < n && cur.y >= 0 && cur.y < m && t[cur.x][cur.y] > cur.t){
            t[cur.x][cur.y] = cur.t;
            if(a[cur.x][cur.y] == 'X') continue;
            bfs.push({cur.x-1, cur.y, cur.t + df(a[cur.x][cur.y], 'N')});
            bfs.push({cur.x, cur.y+1, cur.t + df(a[cur.x][cur.y], 'E')});
            bfs.push({cur.x+1, cur.y, cur.t + df(a[cur.x][cur.y], 'S')});
            bfs.push({cur.x, cur.y-1, cur.t + df(a[cur.x][cur.y], 'W')});
        }
    }
    if(t[n-1][m-1] == INT_MAX) cout << "-1\n";
    else cout << t[n-1][m-1] << '\n';
    return 0;
}

Compilation message

adventure.cpp: In function 'long long int df(char, char)':
adventure.cpp:13:1: warning: control reaches end of non-void function [-Wreturn-type]
   13 | }
      | ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 352 KB Output is correct
3 Correct 1 ms 352 KB Output is correct
4 Correct 1 ms 352 KB Output is correct
5 Correct 1 ms 352 KB Output is correct
6 Correct 1 ms 480 KB Output is correct
7 Correct 2 ms 352 KB Output is correct
8 Correct 1 ms 352 KB Output is correct
9 Correct 1 ms 356 KB Output is correct
10 Correct 1 ms 352 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 352 KB Output is correct
3 Correct 1 ms 352 KB Output is correct
4 Correct 1 ms 352 KB Output is correct
5 Correct 1 ms 352 KB Output is correct
6 Correct 1 ms 480 KB Output is correct
7 Correct 2 ms 352 KB Output is correct
8 Correct 1 ms 352 KB Output is correct
9 Correct 1 ms 356 KB Output is correct
10 Correct 1 ms 352 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 476 KB Output is correct
15 Correct 1 ms 504 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 464 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 352 KB Output is correct
20 Correct 2 ms 508 KB Output is correct

Subtask #3
12.0 / 12.0

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

Subtask #4
16.0 / 16.0

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

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 352 KB Output is correct
3 Correct 1 ms 352 KB Output is correct
4 Correct 1 ms 352 KB Output is correct
5 Correct 1 ms 352 KB Output is correct
6 Correct 1 ms 480 KB Output is correct
7 Correct 2 ms 352 KB Output is correct
8 Correct 1 ms 352 KB Output is correct
9 Correct 1 ms 356 KB Output is correct
10 Correct 1 ms 352 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 476 KB Output is correct
15 Correct 1 ms 504 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 464 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 352 KB Output is correct
20 Correct 2 ms 508 KB Output is correct
21 Correct 1 ms 476 KB Output is correct
22 Correct 1 ms 352 KB Output is correct
23 Correct 1 ms 352 KB Output is correct
24 Correct 1 ms 476 KB Output is correct
25 Correct 1 ms 508 KB Output is correct
26 Correct 1 ms 352 KB Output is correct
27 Correct 2 ms 352 KB Output is correct
28 Correct 2 ms 480 KB Output is correct
29 Correct 4 ms 352 KB Output is correct
30 Correct 4 ms 352 KB Output is correct
31 Correct 2 ms 352 KB Output is correct
32 Correct 1 ms 480 KB Output is correct
33 Correct 1 ms 352 KB Output is correct
34 Correct 1 ms 352 KB Output is correct
35 Correct 230 ms 1844 KB Output is correct
36 Correct 1 ms 352 KB Output is correct
37 Correct 157 ms 2128 KB Output is correct
38 Correct 2 ms 736 KB Output is correct
39 Execution timed out 2098 ms 19016 KB Time limit exceeded
40 Halted 0 ms 0 KB -