Submission #861048

#	Time	Username	Problem	Language	Result	Execution time	Memory
861048		Ellinor	Portals (BOI14_portals)	C++14	20 / 100	3 ms	2140 KiB

portals

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("Ofast,inline") // Ofast = O3,fast-math,allow-store-data-races,no-protect-parens
#pragma GCC optimize ("unroll-loops")

#pragma GCC target("bmi,bmi2,lzcnt,popcnt")                      // bit manipulation
#pragma GCC target("movbe")                                      // byte swap
#pragma GCC target("aes,pclmul,rdrnd")                           // encryption
#pragma GCC target("avx,avx2,f16c,fma,sse3,ssse3,sse4.1,sse4.2")

typedef long long ll;
#define rep(i, a, b) for (int i = (a); i < int(b); i++)
#define rrep(i, a, b) for (int i = (a) - 1; i >= int(b); i--)
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define pb push_back

inline void fast() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); }

ll INF = 1000000000;
ll mod = 1e9 + 7;

#define int ll
#define float double

//

int R, C;
vector<string> grid;

pii S;
pii Ca;

vector<vector<int>> lr, rl, ud, du, visited;

int32_t main()
{
    fast();
    cin >> R >> C;
    grid.assign(R, "");
    rep(i,0,R) {
        cin >> grid[i];
        rep(j,0,C) {
            if (grid[i][j] == 'S') S = {i, j};
            if (grid[i][j] == 'C') Ca = {i, j};
        }
    }
    lr.assign(R, vector<int>(C, -1));
    rl.assign(R, vector<int>(C, -1));
    ud.assign(R, vector<int>(C, -1));
    du.assign(R, vector<int>(C, -1));

    //

    rep(i,0,R) { // lr
        lr[i][0] = 0;
        rep(j,1,C) {
            if (grid[i][j - 1] == '#') lr[i][j] = j;
            else lr[i][j] = lr[i][j - 1];
        }
    }
    rep(i,0,R) { // rl
        rl[i][C-1] = C-1;
        rrep(j,C-1,0) {
            if (grid[i][j + 1] == '#') rl[i][j] = j;
            else rl[i][j] = rl[i][j + 1];
        }
    }

    rep(j,0,C) { // ud
        ud[0][j] = 0;
        rep(i,1,R) {
            if (grid[i - 1][j] == '#') ud[i][j] = i;
            else ud[i][j] = ud[i - 1][j];
        }
    }
    rep(j,0,C) { // du
        du[R - 1][j] = R - 1;
        rrep(i,R - 1, 0) {
            if (grid[i + 1][j] == '#') du[i][j] = i;
            else du[i][j] = du[i + 1][j];
        }
    }

    //

    visited.assign(R, vector<int>(C, -1));
    visited[S.first][S.second] = 0;
    queue<pii> q;
    q.push(S);

    int r, c, steps;
    while (!q.empty())
    {
        pii x = q.front();
        q.pop();
        r = x.first;
        c = x.second;

        if (grid[r][c] == '#') {
            visited[r][c] = 0;
            continue;
        }
        steps = visited[r][c];

        // walk

        if (r - 1 >= 0) {
            if (visited[r - 1][c] == -1) {
                visited[r - 1][c] = steps + 1;
                q.push({r - 1, c});
            }
        }
        if (r + 1 < R) {
            if (visited[r + 1][c] == -1) {
                visited[r + 1][c] = steps + 1;
                q.push({r + 1, c});
            }
        }
        if (c - 1 >= 0) {
            if (visited[r][c - 1] == -1) {
                visited[r][c - 1] = steps + 1;
                q.push({r, c - 1});
            }
        }
        if (c + 1 < C) {
            if (visited[r][c + 1] == -1) {
                visited[r][c + 1] = steps + 1;
                q.push({r, c + 1});
            }
        }

        // portal
        bool u = false;
        if (r == 0) u = true;
        else if (grid[r - 1][c] == '#') u = true;
        bool d = false;
        if (r == R - 1) d = true;
        else if (grid[r + 1][c] == '#') d = true;
        bool l = false;
        if (c == 0) l = true;
        else if (grid[r][c - 1] == '#') l = true;
        bool ri = false;
        if (c == C - 1) ri = true;
        else if (grid[r][c + 1] == '#') ri = true;

        bool p = u || d || l || ri;

        if (p) {
            if (visited[du[r][c]][c] == -1) {
                visited[du[r][c]][c] = steps + 1;
                q.push({du[r][c], c});
            }
            if (visited[ud[r][c]][c] == -1) {
                visited[ud[r][c]][c] = steps + 1;
                q.push({ud[r][c], c});
            }
            if (visited[r][rl[r][c]] == -1) {
                visited[r][rl[r][c]] = steps + 1;
                q.push({r, rl[r][c]});
            }
            if (visited[r][lr[r][c]] == -1) {
                visited[r][lr[r][c]] = steps + 1;
                q.push({r, lr[r][c]});
            }
        }
    }

    cout << visited[Ca.first][Ca.second] << "\n";

    // cerr << endl;
    // rep(i,0,R) {
    //     rep(j, 0, C) {
    //         cerr << visited[i][j] << " ";
    //     }
    //     cerr << endl;
    // }
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 20
• Subtask 3: 20 / 20
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30