Submission #942967

#	Time	Username	Problem	Language	Result	Execution time	Memory
942967		beepbeepsheep	Portals (BOI14_portals)	C++17	100 / 100	165 ms	158212 KiB

portals

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ii pair<ll,ll>

const ll maxn=1005;
char grid[maxn][maxn];
ll dis[maxn][maxn];
ii wall[maxn][maxn][4]; //N,E,S,W
ll hasWall[maxn][maxn];
ll dx[4]={1,0,-1,0};
ll dy[4]={0,1,0,-1};
vector<ii> v[1000005];
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll r,c;
    ii s,e;
    cin>>r>>c;
    for (int i=0;i<=r+1;i++){
        for (int j=0;j<=c+1;j++){
            grid[i][j]='#';
        }
    }
    for (int i=1;i<=r;i++){
        for (int j=1;j<=c;j++){
            cin>>grid[i][j];
            if (grid[i][j]=='S') s={i,j};
            if (grid[i][j]=='C') e={i,j};
        }
    }
    memset(dis,63,sizeof(dis));
    memset(hasWall,63,sizeof(hasWall));
    for (int i=1;i<=r;i++){
        ii p={0,0};
        ll cnt=0;
        for (int j=0;j<=c+1;j++){
            if (grid[i][j]=='#')
                p={i,j+1},cnt=0;
            else{
                wall[i][j][0]=p;
                cnt++;
                hasWall[i][j]=min(hasWall[i][j],cnt);
            }
            //first open square
        }
    }
    for (int i=1;i<=c;i++){
        ii p={0,0};
        ll cnt=0;
        for (int j=0;j<=r+1;j++){
            if (grid[j][i]=='#'){
                p={j+1,i},cnt=0;
            }
            else{
                cnt++;
                wall[j][i][1]=p;
                hasWall[j][i]=min(hasWall[j][i],cnt);
            }
        }
    }
    for (int i=1;i<=r;i++){
        ii p={0,0};
        ll cnt=0;
        for (int j=c+1;j>=0;j--){
            if (grid[i][j]=='#')
                p={i,j-1}, cnt=0;
            else{
                cnt++;
                wall[i][j][2]=p;
                hasWall[i][j]=min(hasWall[i][j],cnt);
            }
        }
    }
    for (int i=1;i<=c;i++){
        ii p={0,0};
        ll cnt=0;
        for (int j=r+1;j>=0;j--){
            if (grid[j][i]=='#'){
                p={j-1,i};
                cnt=0;
            }
            else{
                cnt++;
                wall[j][i][3]=p;
                hasWall[j][i]=min(hasWall[j][i],cnt);
            }
        }
    }
    v[0].emplace_back(s);
    cerr<<1<<endl;
    ll d=0;
    while (d!=1000005){
        ll x,y;
        while (v[d].empty()) d++;
        tie(x,y)=v[d].back();
        //cerr<<d<<' '<<x<<' '<<y<<endl;
        v[d].pop_back();
        if (dis[x][y]<=d) continue;
        dis[x][y]=d;
        if (make_pair(x,y)==e) break;
        for (int i=0;i<4;i++){
            ll nx=wall[x][y][i].first,ny=wall[x][y][i].second;
            if (dis[nx][ny]<=d+hasWall[x][y]) continue;
            v[d+hasWall[x][y]].emplace_back(nx,ny);
        }
        for (int i=0;i<4;i++){
            ll nx=x+dx[i],ny=y+dy[i];
            if (grid[nx][ny]=='#') continue;
            if (dis[nx][ny]<=d+1) continue;
            v[d+1].emplace_back(nx,ny);
        }
    }
    cout<<dis[e.first][e.second];
    return 0;
}

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