Submission #727450

#	Time	Username	Problem	Language	Result	Execution time	Memory
727450		_martynas	Portals (BOI14_portals)	C++11	100 / 100	389 ms	47432 KiB

portals

// THE CAKE IS A LIE!
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;

const int MOD = 1e9+7;

#define F first
#define S second
#define MP make_pair
#define PB push_back
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()

const int MXN = 1005;
const int INF = 1e7;

int n, m, si, sj, fi, fj;
string A[MXN];
bool visited[MXN][MXN];
int to_wall[MXN][MXN];
pii go[4][MXN][MXN];
int dist[MXN][MXN];

const int dirI[] = {-1, 1, 0, 0};
const int dirJ[] = {0, 0, -1, 1};

bool in(int i, int j) {
    return i < n && j < m && i >= 0 && j >= 0;
}

int main() {
    cin >> n >> m;
    for(int i = 0; i < n; i++) cin >> A[i];
    for(int i = 0; i < n; i++)
    for(int j = 0; j < m; j++) {
        if(A[i][j] == 'S') {
            si = i, sj = j;
        }
        if(A[i][j] == 'C') {
            fi = i, fj = j;
        }
    }
    queue<pii> Q;
    for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) to_wall[i][j] = INF;
    for(int i = 0; i < n; i++)
    for(int j = 0; j < m; j++) {
        if(A[i][j] == '#') to_wall[i][j] = 0, Q.push({i, j});
    }
    for(int i = 0; i < n; i++)
    for(int j = 0; j < m; j++) {
        if(A[i][j] != '#' && (i == 0 || j == 0 || i == n-1 || j == m-1)) to_wall[i][j] = 1, Q.push({i, j});
    }
    while(!Q.empty()) {
        int i = Q.front().F;
        int j = Q.front().S;
        Q.pop();
        for(int k = 0; k < 4; k++) {
            int ii = i+dirI[k], jj = j+dirJ[k];
            if(!in(ii, jj)) continue;
            if(to_wall[ii][jj] > to_wall[i][j]+1) {
                to_wall[ii][jj] = to_wall[i][j]+1;
                Q.push({ii, jj});
            }
        }
    }
    for(int k = 0; k < 4; k++) {
        int di = dirI[k] == 1 ? -1 : 1;
        int dj = dirJ[k] == 1 ? -1 : 1;
        for(int i = (di == -1 ? n-1 : 0); i != (di == -1 ? -1 : n); i += di) {
            for(int j = (dj == -1 ? m-1 : 0); j != (dj == -1 ? -1 : m); j += dj) {
                int ii = i+dirI[k], jj = j+dirJ[k];
                if(!in(ii, jj) || A[ii][jj] == '#') {
                    go[k][i][j] = {i, j};
                }
                else {
                    go[k][i][j] = go[k][ii][jj];
                }
            }
        }
    }
    for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) dist[i][j] = INF;
    dist[si][sj] = 0;
    priority_queue<pair<int, pii>, vector<pair<int, pii>>, greater<pair<int, pii>>> PQ;
    PQ.push({dist[si][sj], {si, sj}});
    while(!PQ.empty()) {
        int i = PQ.top().S.F;
        int j = PQ.top().S.S;
        PQ.pop();
        // normal movement
        for(int k = 0; k < 4; k++) {
            int ii = i+dirI[k], jj = j+dirJ[k];
            if(!in(ii, jj)) continue;
            if(A[ii][jj] == '#') continue;
            if(dist[ii][jj] > dist[i][j]+1) {
                dist[ii][jj] = dist[i][j]+1;
                PQ.push({dist[ii][jj], {ii, jj}});
            }
        }
        // portal go brrrrrrr
        for(int k = 0; k < 4; k++) {
            int ii = go[k][i][j].F, jj = go[k][i][j].S;
            // too bad this violates unweighted bfs
            if(dist[ii][jj] > dist[i][j]+to_wall[i][j]) {
                dist[ii][jj] = dist[i][j]+to_wall[i][j];
                PQ.push({dist[ii][jj], {ii, jj}});
            }
        }
    }
    cout << dist[fi][fj] << "\n";
    return 0;
}

/*
4 4
.#.C
.#.#
....
S...



*/

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