Submission #861114

#	Time	Username	Problem	Language	Result	Execution time	Memory
861114		Ellinor	Portals (BOI14_portals)	C++14	0 / 100	7 ms	768 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;

//
vector<vector<vector<vector<pair<pii, int>>>>> dp;

void sol(int r, int c, int b, pii o, int steps) 
{
    if (grid[r][c] == '#') return; // ?
    bool f = false;
    rep(i, 0, dp[r][c][b].size()) {
        if (dp[r][c][b][i].first.first == o.first && dp[r][c][b][i].first.second == o.second) {
            // return; // dp[r][c][b][i].second; //
            if (dp[r][c][b][i].second <= steps) return;
            else dp[r][c][b][i].second = steps;
            f = true;
        }
    }
    if (!f) dp[r][c][b].push_back({o, steps});
    int nsteps = steps + 1;

    // walk

    vector<pii> ps = {{du[r][c], c}, {ud[r][c], c}, {r, rl[r][c]}, {r, lr[r][c]}};
    rep(i,0,4) {
        if (r - 1 >= 0) {
            sol(r - 1, c, 0, ps[i], nsteps);
        }
        if (r + 1 < R) {
            sol(r + 1, c, 0, ps[i], nsteps);
        }
        if (c - 1 >= 0) {
            sol(r, c - 1, 0, ps[i], nsteps);
        }
        if (c + 1 < C) {
            sol(r, c + 1, 0, ps[i], nsteps);
        }
    }
    if (b == 2) {
        if (r - 1 >= 0) {
            sol(r - 1, c, 2, {-1, -1}, nsteps);
        }
        if (r + 1 < R) {
            sol(r + 1, c, 2, {-1, -1}, nsteps);
        }
        if (c - 1 >= 0) {
            sol(r, c - 1, 2, {-1, -1}, nsteps);
        }
        if (c + 1 < C) {
            sol(r, c + 1, 2, {-1, -1}, nsteps);
        }
    }

    // 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 ((b == 1) || (b == 2 && p)) {
        rep(i,0,4) {
            sol(ps[i].first, ps[i].second, 1, {-1, -1}, nsteps);
        }
    }
    else if (o.first != -1 && o.second != -1 && p) { //
        sol(o.first, o.second, 1, {-1, -1}, nsteps);
    }
}

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));

    //

    dp.assign(R, vector<vector<vector<pair<pii, int>>>>(C, vector<vector<pair<pii, int>>>(3, vector<pair<pii, int>>())));

    //

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

    //
    sol(S.first, S.second, 2, {-1, -1}, 0);
    //

    ll aa = INF;
    rep(i,0,3) {
        rep(j,0,dp[Ca.first][Ca.second][i].size()) {
            aa = min(aa, dp[Ca.first][Ca.second][i][j].second);
        }
    }

    cout << aa << "\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: 0 / 20
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30