Submission #1160058

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160058		Ludissey	Portals (BOI14_portals)	C++20	51 / 100	8 ms	3912 KiB

portals

#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define int long long
using namespace std;



signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int r,c; cin >> r >> c; 
    vector<vector<bool>> wall(r,vector<bool>(c, false));

    vector<vector<int>> distPORTAL(r,vector<int>(c, 1e9));
    vector<vector<bool>> visitPORTAL(r,vector<bool>(c, false));

    vector<vector<vector<int>>> portal(r,vector<vector<int>>(c, vector<int>(4,0)));
    pair<int,int> s,e;
    for (int i = 0; i < r; i++)
    {
        for (int j = 0; j < c; j++)
        {
            char ch; cin >> ch;
            if(ch=='#') wall[i][j]=true;
            if(ch=='S') s={i,j};
            if(ch=='C') e={i,j};
        }
    }

    for (int i = 0; i < r; i++)
    {
        int last=0;
        for (int j = 0; j < c; j++)
        {
            if(wall[i][j]) last=j+1;
            portal[i][j][0]=last;
        }
        last=c-1;
        for (int j = c-1; j >= 0; j--)
        {
            if(wall[i][j]) last=j-1;
            portal[i][j][1]=last;
        }
    }

    for (int j = 0; j < c; j++)
    {
        int last=0;
        for (int i = 0; i < r; i++)
        {
            if(wall[i][j]) last=i+1;
            portal[i][j][2]=last;
        }
        last=r-1;
        for (int i = r-1; i >= 0; i--)
        {
            if(wall[i][j]) last=i-1;
            portal[i][j][3]=last;
        }
    }
    queue<pair<int,int>> qDist;
    for (int i = 0; i < r; i++)
    {
        for (int j = 0; j < c; j++)
        {
            if(portal[i][j][0]==j||portal[i][j][1]==j||portal[i][j][2]==i||portal[i][j][3]==i){
                distPORTAL[i][j]=1;
                qDist.push({i,j});
            }
        }
    }

    while(!qDist.empty()){
        pair<int,int> x=qDist.front(); qDist.pop();
        if(visitPORTAL[x.first][x.second]) continue;
        visitPORTAL[x.first][x.second]=true;
        int od=distPORTAL[x.first][x.second];
        for (int i = -1; i <= 1; i+=2)
        {
            pair<int,int> np={x.first+i,x.second};
            if(np.first>=0&&np.first<r&&np.second>=0&&np.second<c&&!wall[np.first][np.second]&&distPORTAL[np.first][np.second]>od+1){
                distPORTAL[np.first][np.second]=od+1;
                qDist.push(np);
            }
        }
        for (int j = -1; j <= 1; j+=2)
        {
            pair<int,int> np={x.first,x.second+j};
            if(np.first>=0&&np.first<r&&np.second>=0&&np.second<c&&!wall[np.first][np.second]&&distPORTAL[np.first][np.second]>od+1){
                distPORTAL[np.first][np.second]=od+1;
                qDist.push(np);
            }
        }
    }


    queue<pair<int,int>> q;
    vector<vector<int>> dist(r,vector<int>(c, 1e9));
    vector<vector<bool>> visited(r,vector<bool>(c, false));
    dist[s.first][s.second]=0;
    q.push(s);

    while(!q.empty()){
        pair<int,int> x=q.front(); q.pop();
        if(visited[x.first][x.second]) continue;
        visited[x.first][x.second]=true;
        int od=dist[x.first][x.second];
        for (int i = -1; i <= 1; i+=2)
        {
            pair<int,int> np={x.first+i,x.second};
            if(np.first>=0&&np.first<r&&np.second>=0&&np.second<c&&!wall[np.first][np.second]&&dist[np.first][np.second]>od+1){
                dist[np.first][np.second]=od+1;
                q.push(np);
            }
        }
        for (int j = -1; j <= 1; j+=2)
        {
            pair<int,int> np={x.first,x.second+j};
            if(np.first>=0&&np.first<r&&np.second>=0&&np.second<c&&!wall[np.first][np.second]&&dist[np.first][np.second]>od+1){
                dist[np.first][np.second]=od+1;
                q.push(np);
            }
        }
        int dp=distPORTAL[x.first][x.second];
        pair<int,int> np={x.first,portal[x.first][x.second][0]};
        if(np.first>=0&&np.first<r&&np.second>=0&&np.second<c&&!wall[np.first][np.second]&&dist[np.first][np.second]>od+dp){
            dist[np.first][np.second]=od+dp;
            q.push(np);
        }
        np={x.first,portal[x.first][x.second][1]};
        if(np.first>=0&&np.first<r&&np.second>=0&&np.second<c&&!wall[np.first][np.second]&&dist[np.first][np.second]>od+dp){
            dist[np.first][np.second]=od+dp;
            q.push(np);
        }
        np={portal[x.first][x.second][2],x.second};
        if(np.first>=0&&np.first<r&&np.second>=0&&np.second<c&&!wall[np.first][np.second]&&dist[np.first][np.second]>od+dp){
            dist[np.first][np.second]=od+dp;
            q.push(np);
        }
        np={portal[x.first][x.second][3],x.second};
        if(np.first>=0&&np.first<r&&np.second>=0&&np.second<c&&!wall[np.first][np.second]&&dist[np.first][np.second]>od+dp){
            dist[np.first][np.second]=od+dp;
            q.push(np);
        }
    }
    cout << dist[e.first][e.second] << "\n";
    return 0;
}

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