oj.uz

Submission #962590

# Submission time Handle Problem Language Result Execution time Memory
962590 2024-04-13T22:27:52 Z AtabayRajabli Awesome Arrowland Adventure (eJOI19_adventure) C++17
100 / 100
 20 ms 8536 KB 
#include <bits/stdc++.h>

// author : a1abay

#define all(v)      v.begin(), v.end()
#define GCD(a, b)   __gcd(a, b)
#define LCM(a, b)   (a*b / (__gcd(a, b)))
#define int         ll

typedef long long           ll;
const int inf =             1e9 + 7;
const int inff =            (int)1e18 + 7;
const int sz =              5e2 + 5;
using namespace             std;

int n, m;
int a[sz][sz];

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

bool ok(int x, int y)
{
    return 1 <= x && x <= n && 1 <= y && y <= m;
}

signed main()   
{       
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    map<char, int> mp;
    mp['N'] = 0;
    mp['E'] = 1;
    mp['S'] = 2;
    mp['W'] = 3;
    mp['X'] = 4;
    
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            char c;
            cin >> c;
            a[i][j] = mp[c];
        }
    }

    queue<array<int, 2>> q[4];
    q[0].push({1, 1});
    vector<vector<int>> d(n + 1, vector<int>(m + 1, inf));
    d[1][1] = 0;
    int pos = 0, num = 1;
    
    while(num > 0)
    {
        while(q[pos].empty())
        {
            pos = (pos + 1) % 4;
        }
        int x = q[pos].front()[0], y = q[pos].front()[1];
        q[pos].pop();
        num--;
        if(a[x][y] == 4)continue;
        for(int i = 0; i < 4; i++)
        {
            int vx = dx[i] + x;
            int vy = dy[i] + y;
            if(!ok(vx, vy))continue;
            int w = (i <= a[x][y] ? (i + 4 - a[x][y]) % 4 : i - a[x][y]);
            
            if(d[vx][vy] > d[x][y] + w)
            {
                d[vx][vy] = d[x][y] + w;
                q[d[vx][vy] % 4].push({vx, vy});
                num++;
            }
        }
    }
    if(d[n][m] >= inf)d[n][m] = -1;
    cout << d[n][m];
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 464 KB Output is correct
3 Correct 1 ms 500 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 344 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 1 ms 464 KB Output is correct
3 Correct 1 ms 500 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 1 ms 348 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 344 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 504 KB Output is correct

Subtask #3
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 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct

Subtask #4
16.0 / 16.0

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

Subtask #5
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 464 KB Output is correct
3 Correct 1 ms 500 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 1 ms 348 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 344 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 504 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 1 ms 344 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 0 ms 468 KB Output is correct
27 Correct 1 ms 344 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 0 ms 464 KB Output is correct
30 Correct 0 ms 344 KB Output is correct
31 Correct 1 ms 464 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 1 ms 344 KB Output is correct
35 Correct 3 ms 904 KB Output is correct
36 Correct 1 ms 348 KB Output is correct
37 Correct 3 ms 1116 KB Output is correct
38 Correct 2 ms 1680 KB Output is correct
39 Correct 20 ms 4548 KB Output is correct
40 Correct 20 ms 4696 KB Output is correct
41 Correct 8 ms 4440 KB Output is correct
42 Correct 20 ms 4440 KB Output is correct
43 Correct 17 ms 8536 KB Output is correct
44 Correct 8 ms 4444 KB Output is correct