Submission #1029289

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029289		VMaksimoski008	Portals (BOI14_portals)	C++17	100 / 100	209 ms	34788 KiB

portals

#include <bits/stdc++.h>

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
//#define int long long

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using Node = array<int, 3>;

const int mod = 1e9 + 7;
const int LOG = 20;
const int maxn = 1e5 + 5;

int dr[8] = {0, -1, 0, 1, 1, 1, -1, -1};
int dc[8] = {-1, 0, 1, 0, 1, -1, 1, -1};
int U[1005][1005], R[1005][1005], L[1005][1005], D[1005][1005];
int D1[1005][1005], vis[1005][1005], dist[1005][1005];
char mat[1005][1005];

signed main() {
    int n, m;
    cin >> n >> m;

    pii S, C;
    for(int i=0; i<=n+1; i++)
        for(int j=0; j<=m+1; j++) mat[i][j] = '#';

    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            cin >> mat[i][j];
            if(mat[i][j] == 'S') S = { i, j };
            if(mat[i][j] == 'C') C = { i, j };
        }
    }

    for(int i=1; i<=n; i++) {
        int last = 0;
        for(int j=1; j<=m; j++) {
            if(mat[i][j] == '#') last = j;
            L[i][j] = last + 1;
        }

        last = m+1;
        for(int j=m; j>=1; j--) {
            if(mat[i][j] == '#') last = j;
            R[i][j] = last - 1;
        }
    }

    for(int j=1; j<=m; j++) {
        int last = 0;
        for(int i=1; i<=n; i++) {
            if(mat[i][j] == '#') last = i;
            U[i][j] = last + 1;
        }

        last = n+1;
        for(int i=n; i>=1; i--) {
            if(mat[i][j] == '#') last = i;
            D[i][j] = last - 1;
        }
    }

    queue<pii> q;
    for(int i=0; i<=n+1; i++) {
        for(int j=0; j<=m+1; j++) {
            if(mat[i][j] == '#') q.push({ i, j }), vis[i][j] = 1, D1[i][j] = -1;
            else D1[i][j] = 1e9;
        }
    }

    while(!q.empty()) {
        auto [r, c] = q.front(); q.pop();

        for(int i=0; i<4; i++) {
            int nr = r + dr[i], nc = c + dc[i];
            if(nr < 0 || nr > n + 1 || nc < 0 || nc > m + 1) continue;
            if(vis[nr][nc] || mat[nr][nc] == '#') continue;
            vis[nr][nc] = 1;
            q.push({ nr, nc });
            D1[nr][nc] = D1[r][c] + 1;
        }
    }

    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++) dist[i][j] = 1e9;
    dist[S.first][S.second] = 0;

    priority_queue<Node, vector<Node>, greater<Node> > pq;
    pq.push({ 0, S.first, S.second });

    while(!pq.empty()) {
        auto [d, r, c] = pq.top(); pq.pop();
        if(d != dist[r][c]) continue;

        for(int i=0; i<4; i++) {
            int nr = r + dr[i], nc = c + dc[i];
            if(nr < 1 || nr > n || nc < 1 || nc > m) continue;
            if(mat[nr][nc] == '#') continue;

            if(dist[nr][nc] > dist[r][c] + 1) {
                dist[nr][nc] = d + 1;
                pq.push({ d + 1, nr, nc });
            }
        }

        //try up
        if(dist[U[r][c]][c] > dist[r][c] + D1[r][c] + 1) {
            dist[U[r][c]][c] = dist[r][c] + D1[r][c] + 1;
            pq.push({ dist[r][c] + D1[r][c] + 1, U[r][c], c });
        }

        if(dist[D[r][c]][c] > dist[r][c] + D1[r][c] + 1) {
            dist[D[r][c]][c] = dist[r][c] + D1[r][c] + 1;
            pq.push({ dist[r][c] + D1[r][c] + 1, D[r][c], c });
        }

        if(dist[r][L[r][c]] > dist[r][c] + D1[r][c] + 1) {
            dist[r][L[r][c]] = dist[r][c] + D1[r][c] + 1;
            pq.push({ dist[r][L[r][c]], r, L[r][c] });
        }

        if(dist[r][R[r][c]] > dist[r][c] + D1[r][c] + 1) {
            dist[r][R[r][c]] = dist[r][c] + D1[r][c] + 1;
            pq.push({ dist[r][R[r][c]], r, R[r][c] });
        }
    }

    // for(int i=1; i<=n; i++) {
    //     for(int j=1; j<=m; j++) cout << (dist[i][j] == 1e9 ? -1 : dist[i][j]) << " ";
    //     cout << '\n';
    // }

    cout << dist[C.first][C.second] << '\n';
    return 0;
}

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