Submission #534063

#	Time	Username	Problem	Language	Result	Execution time	Memory
534063		perchuts	Portals (BOI14_portals)	C++17	100 / 100	274 ms	50748 KiB

portals

#include <bits/stdc++.h>
#define maxn (int)(1e5+51)
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define ll long long
#define pb push_back
#define ull unsigned long long
#define ii pair<int,int>
#define iii tuple<int,int,int>
#define inf 2000000001
#define mod 1000000007 //998244353
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;

template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }

char grid[1005][1005];
bool vis[1005][1005];
int walldist[1005][1005], dist[1005][1005], a[8] = {1,-1,0,0,0,0,1,-1}, n, m;
ii nearest[1005][1005][4];
vector<ii>walls;

bool valid(int x,int y){return x>=0&&y>=0&&x<=n+1&&y<=m+1;}

void bfs1(ii start){
    auto [u,v] = start;
    queue<ii>q;q.push(start);
    vis[u][v] = 1;
    while(!q.empty()){
        auto [x,y] = q.front();q.pop();
        for(int i=0;i<4;++i){
            int x2 = x+a[i],y2=y+a[i+4];
            if(valid(x2,y2)&&!vis[x2][y2]){
                vis[x2][y2]=1;
                if(grid[x2][y2]=='#')walls.pb({x2,y2});
                else q.push({x2,y2});
            }
        }
    }
}

void bfs2(){

    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            walldist[i][j] = inf;

    queue<ii>q;
    for(auto x:walls){
        q.push(x);
        walldist[x.first][x.second] = 0;
    }

    while(!q.empty()){
        auto [x,y] = q.front();q.pop();
        for(int i=0;i<4;++i){
            int x2 = x + a[i], y2 = y + a[i+4];
            if(valid(x2,y2)&&walldist[x2][y2]==inf){
                walldist[x2][y2] = walldist[x][y]+1;
                q.push({x2,y2});
            }
        }
    }
}

int b[8] = {0,1,0,-1,-1,0,1,0};
int bfs3(ii start,ii target){
    priority_queue<pair<int,ii>,vector<pair<int,ii>>,greater<pair<int,ii>>>pq;
    pq.push({0,start});
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            dist[i][j] = inf;
    dist[start.first][start.second] = 0;
    while(!pq.empty()){
        auto [d,p] = pq.top();
        pq.pop();
        auto [x,y] = p;
        if(d>dist[x][y])continue;
        for(int i=0;i<4;++i){//normal adjacency
            int x2 = x + a[i], y2 = y + a[i+4];
            if(valid(x2,y2)&&grid[x2][y2]!='#'&&ckmin(dist[x2][y2],d+1)){
                pq.push({dist[x2][y2],{x2,y2}});
            }
        }        
        //now portal adjacency
        for(int i=0;i<4;++i){
            auto [x2,y2] = nearest[x][y][i];
            x2+=b[i],y2+=b[i+4];
            if(ckmin(dist[x2][y2],d+walldist[x][y]))pq.push({dist[x2][y2],{x2,y2}});
        }
    }
    return dist[target.first][target.second];
}

int main(){_
    cin>>n>>m;
    ii start,target;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            cin>>grid[i][j];
            if(grid[i][j]=='S')start={i,j};
            if(grid[i][j]=='C')target={i,j};
        }
    }
    for(int i=0;i<=n;++i)grid[i][0]=grid[i][m+1]='#';
    for(int j=0;j<=m;++j)grid[0][j]=grid[n+1][j]='#';
    bfs1(start);//find walls
    bfs2();//get distance from each open square to nearest wall

    //nearest: 0 => direita, 1=> subindo, 2=> esquerda, 3=>descendo
    
    for(int i=0;i<=n+1;++i){
        for(int j=m+1;~j;j--)nearest[i][j][0] = {i,(grid[i][j]=='#'?j:nearest[i][j+1][0].second)};
        for(int j=0;j<=m+1;++j)nearest[i][j][2] = {i,(grid[i][j]=='#'?j:nearest[i][j-1][2].second)};
    }
    for(int j=0;j<=m+1;++j){
        for(int i=0;i<=n+1;++i)nearest[i][j][1] = {(grid[i][j]=='#'?i:nearest[i-1][j][1].first),j};
        for(int i=n+1;~i;--i)nearest[i][j][3] = {(grid[i][j]=='#'?i:nearest[i+1][j][3].first),j};
    }

    cout<<bfs3(start,target)<<endl;   
}

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