Submission #731429

#	Time	Username	Problem	Language	Result	Execution time	Memory
731429		Trunkty	Portals (BOI14_portals)	C++14	100 / 100	742 ms	83520 KiB

portals

#include <bits/extc++.h>
using namespace std;
typedef long long ll;
#define int ll

int r,c,sx,sy,fx,fy;
char grid[1005][1005];
int dist[1005][1005],lef[1005][1005],rit[1005][1005],up[1005][1005],down[1005][1005];
bool check[1005][1005];
int dp[1005][1005];
bool check2[1005][1005];

signed main(){
	//ios_base::sync_with_stdio(false);
	//cin.tie(NULL);
    cin >> r >> c;
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            cin >> grid[i][j];
            if(grid[i][j]=='S'){
                sx = i;
                sy = j;
                grid[i][j] = '.';
            }
            else if(grid[i][j]=='C'){
                fx = i;
                fy = j;
                grid[i][j] = '.';
            }
            dp[i][j] = 2e9;
        }
    }
    priority_queue<vector<int>,vector<vector<int>>,greater<vector<int>>> pq;
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            if(grid[i][j]=='.' and grid[i-1][j]=='.' and grid[i+1][j]=='.' and grid[i][j-1]=='.' and grid[i][j+1]=='.'){
                dist[i][j] = 2e9;
            }
            else if(grid[i][j]=='.'){
                pq.push({dist[i][j],i,j});
            }
        }
    }
    while(pq.size()>0){
        while(pq.size()>0 and check[pq.top()[1]][pq.top()[2]]){
            pq.pop();
        }
        if(pq.size()==0){
            break;
        }
        int x = pq.top()[1], y = pq.top()[2];
        pq.pop();
        check[x][y] = true;
        if(grid[x-1][y]=='.' and dist[x-1][y]>dist[x][y]+1){
            dist[x-1][y] = dist[x][y]+1;
            pq.push({dist[x-1][y],x-1,y});
        }
        if(grid[x+1][y]=='.' and dist[x+1][y]>dist[x][y]+1){
            dist[x+1][y] = dist[x][y]+1;
            pq.push({dist[x+1][y],x+1,y});
        }
        if(grid[x][y-1]=='.' and dist[x][y-1]>dist[x][y]+1){
            dist[x][y-1] = dist[x][y]+1;
            pq.push({dist[x][y-1],x,y-1});
        }
        if(grid[x][y+1]=='.' and dist[x][y+1]>dist[x][y]+1){
            dist[x][y+1] = dist[x][y]+1;
            pq.push({dist[x][y+1],x,y+1});
        }
    }
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            if(grid[i][j-1]!='.'){
                lef[i][j] = j;
            }
            else{
                lef[i][j] = lef[i][j-1];
            }
        }
        for(int j=c;j>=1;j--){
            if(grid[i][j+1]!='.'){
                rit[i][j] = j;
            }
            else{
                rit[i][j] = rit[i][j+1];
            }
        }
    }
    for(int j=1;j<=c;j++){
        for(int i=1;i<=r;i++){
            if(grid[i-1][j]!='.'){
                up[i][j] = i;
            }
            else{
                up[i][j] = up[i-1][j];
            }
        }
        for(int i=r;i>=1;i--){
            if(grid[i+1][j]!='.'){
                down[i][j] = i;
            }
            else{
                down[i][j] = down[i+1][j];
            }
        }
    }
    dp[sx][sy] = 0;
    pq.push({0,sx,sy});
    while(pq.size()>0){
        while(pq.size()>0 and check2[pq.top()[1]][pq.top()[2]]){
            pq.pop();
        }
        if(pq.size()==0){
            break;
        }
        int x = pq.top()[1], y = pq.top()[2];
        pq.pop();
        check2[x][y] = true;
        if(grid[x-1][y]=='.' and dp[x-1][y]>dp[x][y]+1){
            dp[x-1][y] = dp[x][y]+1;
            pq.push({dp[x-1][y],x-1,y});
        }
        if(grid[x+1][y]=='.' and dp[x+1][y]>dp[x][y]+1){
            dp[x+1][y] = dp[x][y]+1;
            pq.push({dp[x+1][y],x+1,y});
        }
        if(grid[x][y-1]=='.' and dp[x][y-1]>dp[x][y]+1){
            dp[x][y-1] = dp[x][y]+1;
            pq.push({dp[x][y-1],x,y-1});
        }
        if(grid[x][y+1]=='.' and dp[x][y+1]>dp[x][y]+1){
            dp[x][y+1] = dp[x][y]+1;
            pq.push({dp[x][y+1],x,y+1});
        }
        if(dp[x][lef[x][y]]>dp[x][y]+dist[x][y]+1){
            dp[x][lef[x][y]] = dp[x][y]+dist[x][y]+1;
            pq.push({dp[x][lef[x][y]],x,lef[x][y]});
        }
        if(dp[x][rit[x][y]]>dp[x][y]+dist[x][y]+1){
            dp[x][rit[x][y]] = dp[x][y]+dist[x][y]+1;
            pq.push({dp[x][rit[x][y]],x,rit[x][y]});
        }
        if(dp[up[x][y]][y]>dp[x][y]+dist[x][y]+1){
            dp[up[x][y]][y] = dp[x][y]+dist[x][y]+1;
            pq.push({dp[up[x][y]][y],up[x][y],y});
        }
        if(dp[down[x][y]][y]>dp[x][y]+dist[x][y]+1){
            dp[down[x][y]][y] = dp[x][y]+dist[x][y]+1;
            pq.push({dp[down[x][y]][y],down[x][y],y});
        }
    }
    cout << dp[fx][fy] << "\n";
	return 0;
}

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