답안 #654968

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
654968 2022-11-02T09:26:37 Z KiriLL1ca Portal (COCI17_portal) C++14
120 / 120
71 ms 9948 KB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fr first
#define sc second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pw(x) (1ll << x)
#define sz(x) (int)((x).size())
#define pb push_back
#define endl '\n'
#define mp make_pair
#define vec vector

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef unsigned long long ull;
typedef unsigned int uint;

template <typename T> inline bool umin (T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; }
template <typename T> inline bool umax (T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template <typename T>
using oset = tree<T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

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

const int N = 505;
const int inf = 1e9 + 127;
char a[N][N];
int d[N][N];
pii go[N][N][4];

inline void solve () {
        int n, m; cin >> n >> m;
        pii s, f;
        for (int i = 0; i < n; ++i) {
                for (int j = 0; j < m; ++j) {
                        cin >> a[i][j];
                        if (a[i][j] == 'C') s = {i, j};
                        if (a[i][j] == 'F') f = {i, j};
                        d[i][j] = inf;
                }
        }

        for (int i = 0; i < n; ++i) {
                int lst = -1;
                for (int j = 0; j < m; ++j) {
                        if (a[i][j] == '#') lst = j;
                        go[i][j][0] = {i, lst + 1};
                }

                lst = m;
                for (int j = m - 1; j >= 0; --j) {
                        if (a[i][j] == '#') lst = j;
                        go[i][j][1] = {i, lst - 1};
                }
        }
        for (int j = 0; j < m; ++j) {
                int lst = -1;
                for (int i = 0; i < n; ++i) {
                        if (a[i][j] == '#') lst = i;
                        go[i][j][2] = {lst + 1, j};
                }

                lst = n;
                for (int i = n - 1; i >= 0; --i) {
                        if (a[i][j] == '#') lst = i;
                        go[i][j][3] = {lst - 1, j};
                }
        }

        priority_queue <array <int, 3>, vector <array <int, 3>>, greater <array <int, 3>>> pq;
        d[s.fr][s.sc] = 0; pq.push({0, s.fr, s.sc});

        function <bool(int, int)> valid = [&] (int x, int y) { return x >= 0 && y >= 0 && x < n && y < m; };
        function <int(int, int, int, int)> dist = [&] (int x, int y, int xx, int yy) { return abs(x - xx) + abs(y - yy); };

        while (sz(pq)) {
                auto [dis, x, y] = pq.top(); pq.pop();
                if (dis > d[x][y]) continue;
                /// little step
                for (int i = 0; i < 4; ++i) {
                        int nx = x + dx[i], ny = y + dy[i];
                        if (valid(nx, ny) && a[nx][ny] != '#' && umin(d[nx][ny], d[x][y] + 1)) pq.push({d[nx][ny], nx, ny});
                }

                /// big step
                for (int port1 = 0; port1 < 4; ++port1) {
                        for (int port2 = 0; port2 < 4; ++port2) {
                                if (port1 == port2) continue;
                                auto [qx, qy] = go[x][y][port1];
                                auto [wx, wy] = go[x][y][port2];
                                if (umin(d[wx][wy], d[x][y] + dist(x, y, qx, qy) + 1)) pq.push({d[wx][wy], wx, wy});
                        }
                }
        }
        if (d[f.fr][f.sc] == inf) cout << "nemoguce";
        else cout << d[f.fr][f.sc];
}

signed main() {
        ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
        #ifdef LOCAL
                freopen("input.txt", "r", stdin);
                freopen("output.txt", "w", stdout);
        #endif
        int t = 1; // cin >> t;
        while (t--) solve();
        return 0;
}

Compilation message

portal.cpp: In function 'void solve()':
portal.cpp:85:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   85 |                 auto [dis, x, y] = pq.top(); pq.pop();
      |                      ^
portal.cpp:97:38: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   97 |                                 auto [qx, qy] = go[x][y][port1];
      |                                      ^
portal.cpp:98:38: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   98 |                                 auto [wx, wy] = go[x][y][port2];
      |                                      ^
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 328 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 2260 KB Output is correct
2 Correct 2 ms 1492 KB Output is correct
3 Correct 5 ms 1744 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 3188 KB Output is correct
2 Correct 3 ms 3156 KB Output is correct
3 Correct 9 ms 2260 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 7484 KB Output is correct
2 Correct 24 ms 5020 KB Output is correct
3 Correct 16 ms 5076 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 8660 KB Output is correct
2 Correct 8 ms 9556 KB Output is correct
3 Correct 29 ms 5908 KB Output is correct
4 Correct 32 ms 6808 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 71 ms 9948 KB Output is correct
2 Correct 13 ms 9688 KB Output is correct
3 Correct 47 ms 9712 KB Output is correct
4 Correct 43 ms 9700 KB Output is correct