Submission #654968

#	Time	Username	Problem	Language	Result	Execution time	Memory
654968		KiriLL1ca	Portal (COCI17_portal)	C++14	120 / 120	71 ms	9948 KiB

portal

#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 (stderr)

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];
      |                                      ^

• Subtask 1: 12 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 12 / 12
• Subtask 6: 12 / 12
• Subtask 7: 12 / 12
• Subtask 8: 12 / 12
• Subtask 9: 12 / 12
• Subtask 10: 12 / 12