Submission #1035462

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035462		ByeWorld	Portals (BOI14_portals)	C++14	100 / 100	769 ms	152968 KiB

portals

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
// #define int long long
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
typedef pair<int,int> pii;
typedef pair<int,pii> ipii;
typedef pair<pii,int> iipi;
const int MAXN = 1e3+5;
const int INF = 1e9+10;
void chmn(int &a, int b){ a = min(a, b); }
vector <int> dx = {1, -1, 0, 0};
vector <int> dy = {0, 0, 1, -1};

int n, m, ex, ey, sx, sy;
char s[MAXN][MAXN];
int near[MAXN][MAXN], dis[MAXN][MAXN];
vector <iipi> adj[MAXN][MAXN]; 

bool valid(int x, int y){
    if(x<=0 || y<=0 || x>n || y>m || s[x][y]=='#') return 0;
    return 1;
}

void bfs(){
    for(int i=0; i<=n+1; i++)
        for(int j=0; j<=m+1; j++) near[i][j] = INF;
    queue <pii> q; 
    for(int i=0; i<=n+1; i++){
        for(int j=0; j<=m+1; j++){
            if(s[i][j]=='#') q.push({i, j}), near[i][j] = 0;
        }
    }

    while(!q.empty()){
        int x = q.front().fi, y = q.front().se; q.pop();
        for(int i=0; i<4; i++){
            int nx = x+dx[i], ny = y+dy[i];
            if(valid(nx,ny) && near[nx][ny] > near[x][y]+1){
                near[nx][ny] = near[x][y]+1;
                q.push({nx, ny});
            }
        }
    }
}
void add(int a, int b, int c, int d, int wei){
    if(!valid(a, b) || !valid(c, d)) return;
    adj[a][b].pb({{c, d}, wei});
}

priority_queue <ipii, vector<ipii>, greater<ipii>> pq;
void dji(){
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++) dis[i][j] = INF;
    pq.push({0, {sx, sy}}); dis[sx][sy] = 0;
    
    while(!pq.empty()){
        int dist = pq.top().fi, x = pq.top().se.fi, y = pq.top().se.se;
        pq.pop();
        if(dis[x][y] < dist) continue;
        // cout << x << ' ' << y<< ' ' << dis[x][y] << " xy\n";
        for(auto [id, wei] : adj[x][y]){
            int nx = id.fi, ny = id.se;
            if(valid(nx,ny) && dis[nx][ny] > dis[x][y] + wei){
                dis[nx][ny] = dis[x][y] + wei;
                pq.push({dis[nx][ny], {nx, ny}});
            }
        }
    }
}
signed main(){
    // ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for(int i=0; i<=n+1; i++)
        for(int j=0; j<=m+1; j++) s[i][j] = '#';
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            cin >> s[i][j];
            if(s[i][j] == 'S') sx = i, sy = j;
            if(s[i][j] == 'C') ex = i, ey = j;
        }
    }
    bfs();
    for(int i=1; i<=n; i++){
        int las = 1;
        for(int j=1; j<=m; j++){
            if(s[i][j] == '#') las = j+1;
            else add(i, j, i, las, near[i][j]);
        }
    }
    for(int i=1; i<=n; i++){
        int las = m;
        for(int j=m; j>=1; j--){
            if(s[i][j] == '#') las = j-1;
            else add(i, j, i, las, near[i][j]);
        }
    }
    for(int j=1; j<=m; j++){
        int las = 1;
        for(int i=1; i<=n; i++){
            if(s[i][j] == '#') las = i+1;
            else {
                // cout << i << ' ' << j << ' ' << las << ' ' << j << ' ' << near[i][j] << "near\n";
                add(i, j, las, j, near[i][j]);
            }
        }
    }
    for(int j=1; j<=m; j++){
        int las = n;
        for(int i=n; i>=1; i--){
            if(s[i][j] == '#') las = i-1;
            else add(i, j, las, j, near[i][j]);
        }
    }
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            for(int x=0; x<4; x++)
                add(i, j, i+dx[x], j+dy[x], 1);
    dji();
    cout << dis[ex][ey] << '\n';

    // for(int i=1; i<=n; i++){
    //     for(int j=1; j<=m; j++){
    //         cout << near[i][j] << " \n"[j==m];
    //     }
    // }
}

Compilation message (stderr)

portals.cpp: In function 'void dji()':
portals.cpp:68:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   68 |         for(auto [id, wei] : adj[x][y]){
      |                  ^

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