oj.uz

Submission #788012

# Submission time Handle Problem Language Result Execution time Memory
788012 2023-07-19T16:08:23 Z Chal1shkan Awesome Arrowland Adventure (eJOI19_adventure) C++14
100 / 100
 66 ms 18300 KB 
//Bismillahir-Rahmanir-Rahim

# include <bits/stdc++.h>
 
# define pb push_back
# define ff first
# define ss second
# define nl "\n"
# define sz(x) ((int)(x).size())
# define all(x) (x).begin(), (x).end()
# define deb(x) cerr << #x  << " = " << x << endl; 
# define pll pair <ll, ll>
# define pii pair <int, int>
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
 
const ll maxn = 5e2 + 7;
const ll inf = 2e18 + 0;
const ll mod = 1e9 + 7;
const ll dx[] = {-1, 1, 0, 0};
const ll dy[] = {0, 0, -1, 1};

using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

ll n, m;
char c[maxn][maxn];
ll dist[maxn][maxn];

pii dir (char c)
{
    if (c == 'N') return {-1, 0};
    if (c == 'E') return {0, 1};
    if (c == 'S') return {1, 0};
    if (c == 'W') return {0, -1};
}

char f (pii p)
{
    if (p == make_pair(-1, 0)) return 'N';
    if (p == make_pair(0, 1)) return 'E';
    if (p == make_pair(1, 0)) return 'S';
    if (p == make_pair(0, -1)) return 'W';
}

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

ll id (char c)
{
    if (c == 'N') return 0;
    if (c == 'E') return 1;
    if (c == 'S') return 2;
    if (c == 'W') return 3; 
}

ll dst (char a, char b)
{
    ll pos1 = id(a), pos2 = id(b);
    if (pos1 <= pos2) return pos2 - pos1;
    else return 4 - pos1 + pos2;
}

void ma1n (/* SABR */)
{
    cin >> n >> m;
    for (ll i = 1; i <= n; ++i)
    {
        for (ll j = 1; j <= m; ++j)
        {
            cin >> c[i][j];
            dist[i][j] = inf;
        }
    }
    set <pair <ll, pii> > q;
    dist[1][1] = 0;
    q.insert({dist[1][1], {1, 1}});
//  for (char c : {'N', 'E', 'S', 'W'})
//  {
//      for (char b : {'N', 'E', 'S', 'W'})
//      {
//          cout << c << ' ' << b << ' ' << dst(c, b) << nl;
//      }
//  }
//  exit(0);
    while (!q.empty())
    {
        ll x = (q.begin() -> ss.ff);
        ll y = (q.begin() -> ss.ss);
        q.erase(q.begin());
    //  cout << x << ' ' << y << endl;
        if (c[x][y] == 'X') continue;
        for (ll k = 0; k < 4; ++k)
        {
            ll add = dst(c[x][y], f({dx[k], dy[k]}));
            ll nx = x + dx[k];
            ll ny = y + dy[k];
            if (in(nx, ny) && dist[nx][ny] > dist[x][y] + add && (c[nx][ny] != 'X' || (nx == n && ny == m)))
            {
                dist[nx][ny] = dist[x][y] + add;
                q.insert({dist[nx][ny], {nx, ny}});
            }
        }
    }
//    for (ll i = 1; i <= n; ++i)
//    {
//        for (ll j = 1; j <= m; ++j)
//        {
//            cout << dist[i][j] << ' ';
//        }
//        cout << nl;
//    }
    if (dist[n][m] == inf)
    {
        cout << -1 << nl;
    }
    else
    {
        cout << dist[n][m] << nl;
    }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
//  freopen("file.in", "r", stdin);
//  freopen("file.out", "w", stdout);
    int ttt = 1;
//  cin >> ttt;
    for (int test = 1; test <= ttt; ++test)
    {
//      cout << "Case " << test << ":" << '\n';
        ma1n();
    }
    return 0;
}

// 998batrr | BbIWEJI 3A TObOU!!!
// tourist  | BbIWEJI 3A TObOU!!!

Compilation message

adventure.cpp: In function 'std::pair<int, int> dir(char)':
adventure.cpp:38:1: warning: control reaches end of non-void function [-Wreturn-type]
   38 | }
      | ^
adventure.cpp: In function 'char f(std::pair<int, int>)':
adventure.cpp:46:1: warning: control reaches end of non-void function [-Wreturn-type]
   46 | }
      | ^
adventure.cpp: In function 'll id(char)':
adventure.cpp:59:1: warning: control reaches end of non-void function [-Wreturn-type]
   59 | }
      | ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 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 0 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 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 1 ms 212 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 340 KB Output is correct

Subtask #3
12.0 / 12.0

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

Subtask #4
16.0 / 16.0

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

Subtask #5
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 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 1 ms 212 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 0 ms 340 KB Output is correct
23 Correct 0 ms 340 KB Output is correct
24 Correct 0 ms 340 KB Output is correct
25 Correct 0 ms 340 KB Output is correct
26 Correct 0 ms 340 KB Output is correct
27 Correct 0 ms 340 KB Output is correct
28 Correct 0 ms 340 KB Output is correct
29 Correct 0 ms 340 KB Output is correct
30 Correct 0 ms 340 KB Output is correct
31 Correct 0 ms 340 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 0 ms 340 KB Output is correct
34 Correct 0 ms 340 KB Output is correct
35 Correct 5 ms 596 KB Output is correct
36 Correct 1 ms 340 KB Output is correct
37 Correct 5 ms 852 KB Output is correct
38 Correct 1 ms 1492 KB Output is correct
39 Correct 43 ms 2856 KB Output is correct
40 Correct 42 ms 2976 KB Output is correct
41 Correct 4 ms 2772 KB Output is correct
42 Correct 44 ms 2856 KB Output is correct
43 Correct 66 ms 18300 KB Output is correct
44 Correct 3 ms 2772 KB Output is correct