oj.uz

Submission #641892

# Submission time Handle Problem Language Result Execution time Memory
641892 2022-09-17T18:52:56 Z Nelt Awesome Arrowland Adventure (eJOI19_adventure) C++17
100 / 100
 461 ms 15640 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,fma")

#include <bits/stdc++.h>
// #include <ext/pb_ds/detail/standard_policies.hpp>
// #include <windows.h>

/* DEFINES */
#define S second
#define F first
#define ll long long
#define ull unsigned long long
#define ld long double
#define npos ULLONG_MAX
#define INF LLONG_MAX
#define elif else if
#define vv(a) vector<a>
#define pp(a, b) pair<a, b>
#define pq(a) priority_queue<a>
#define qq(a) queue<a>
#define ss(a) set<a>
#define mm(a, b) map<a, b>
#define ump(a, b) unordered_map<a, b>
#define pb push_back
#define sync                      \
    ios_base::sync_with_stdio(0); \
    cin.tie();                    \
    cout.tie();
#define endl "\n"
#define allc(a) begin(a), end(a)
#define all(a) a, a + sizeof(a) / sizeof(a[0])
#define mpr make_pair
#define ins insert
using namespace std;
using namespace __cxx11;
typedef char chr;
typedef basic_string<chr> str;
const int sz = 505;
int n, m, g[sz][sz], d[sz][sz];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
int num[] = {3, 1, 2, 4};
bool can_go(int x, int y)
{
    return (x >= 1 and y >= 1 and x <= n and y <= m);
}
int x, y, c, x2, y2, cnt = 1, cnt1[4];
qq(pp(int, int)) q[4];
void bfs(int sx, int sy)
{
    for (ll i = 1; i <= n; i++)
        fill(d[i], d[i] + m + 1, 1e9);
    d[sx][sy] = 0;
    q[0].push(mpr(sx, sy));
    cnt1[0] = 1;
    while (cnt--)
    {
        pp(int, int) cord;
        for (int i = 0; i < 4; i++)
            if (cnt1[i])
            {
                cord = q[i].front();
                q[i].pop();
                cnt1[i]--;
                break;
            }
        x = cord.F, y = cord.S;
        if (g[x][y] == -1)
            continue;
        for (int k = 0; k < 4; k++)
        {
            c = num[k] - g[x][y];
            c += (c < 0 ? 4 : 0);
            x2 = x + dx[k], y2 = y + dy[k];
            (can_go(x2, y2) && d[x2][y2] > d[x][y] + c) ? q[c].push(mpr(x2, y2)),
                cnt++, cnt1[c]++,
                d[x2][y2] = d[x][y] + c : 0;
        }
    }
}
void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        chr s[m];
        scanf("%s\n", s);
        for (int j = 0; j < m; j++)
        {
            g[i][j + 1] = (s[j] == 'N' ? 1 : s[j] == 'E' ? 2
                                         : s[j] == 'S'   ? 3
                                         : s[j] == 'W'   ? 4
                                                         : -1);
        }
    }
    bfs(1, 1);
    cout << (d[n][m] == 1e9 ? -1 : d[n][m]) << endl;
}
/*

*/
int main()
{
    // sync
    // precomp();
    ll t = 1;
    // cin >> t;
    for (ll i = 1; i <= t; i++)
        // cout << "Case #" << i << ": ",
        solve();
    cerr << "\nTime elapsed : " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\n";
}

Compilation message

adventure.cpp: In function 'void solve()':
adventure.cpp:87:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |         scanf("%s\n", s);
      |         ~~~~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
16.0 / 16.0

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

Subtask #5
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 316 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 316 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 312 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 312 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 316 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 312 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 0 ms 212 KB Output is correct
26 Correct 1 ms 212 KB Output is correct
27 Correct 1 ms 312 KB Output is correct
28 Correct 1 ms 212 KB Output is correct
29 Correct 0 ms 212 KB Output is correct
30 Correct 0 ms 308 KB Output is correct
31 Correct 1 ms 212 KB Output is correct
32 Correct 1 ms 312 KB Output is correct
33 Correct 1 ms 212 KB Output is correct
34 Correct 1 ms 312 KB Output is correct
35 Correct 22 ms 1304 KB Output is correct
36 Correct 1 ms 340 KB Output is correct
37 Correct 16 ms 1156 KB Output is correct
38 Correct 1 ms 1364 KB Output is correct
39 Correct 296 ms 10752 KB Output is correct
40 Correct 461 ms 15640 KB Output is correct
41 Correct 4 ms 2516 KB Output is correct
42 Correct 279 ms 10308 KB Output is correct
43 Correct 17 ms 4564 KB Output is correct
44 Correct 4 ms 2516 KB Output is correct