Submission #1068089

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068089		vjudge1	Portals (BOI14_portals)	C++17	100 / 100	499 ms	159600 KiB

portals

#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
#define vi vector<int>
#define vvi vector<vector<pair<int,int>>> 
#define nel cout<<"\n"
#define f first
#define s second
#define dbg cout<<-1; return

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC target("sse,sse2,ssse3,sse4,abm,mmx,avx,fma")

const int N=1e3+2; 
vector<vector<char>> m(N+1, vector<char>(N+1,'#'));
vector<pair<pair<int,int>,int>> e[N+1][N+1]; int r,c; 
vector<vi> dist_to_wall(N+1, vi(N+1,-1));
int up[N+1][N+1], dn[N+1][N+1], le[N+1][N+1], ri[N+1][N+1]; 
vector<int> dx={1,-1,0,0}, dy={0,0,-1,1};

void calc_dist_wall(vector<pair<int,int>>& wall){
    queue<pair<int,int>> q;
    for(auto i:wall){
        dist_to_wall[i.f][i.s]=0;
        q.push({i.f,i.s});
    }
    while(!q.empty()){
        pair<int,int> cur=q.front(); q.pop();
        for(int i=0; i<4; i++){
            pair<int,int> nxt={cur.f+dx[i], cur.s+dy[i]};
            if(nxt.f<0||nxt.s<0||nxt.f>r+1||nxt.s>c+1) continue;
            if(m[nxt.f][nxt.s]=='#') continue;
            if(dist_to_wall[nxt.f][nxt.s]!=-1) continue;
            dist_to_wall[nxt.f][nxt.s]=dist_to_wall[cur.f][cur.s]+1;
            q.push(nxt);
        }
    }
}

void adds_edge(){
    for(int i=1; i<=r; i++){
        for(int j=1; j<=c; j++){
            if(m[i][j]=='#') continue;
            e[i][j].push_back({{up[i][j],j},dist_to_wall[i][j]});
            e[i][j].push_back({{dn[i][j],j},dist_to_wall[i][j]});
            e[i][j].push_back({{i,le[i][j]},dist_to_wall[i][j]});
            e[i][j].push_back({{i,ri[i][j]},dist_to_wall[i][j]});
            for(int d=0; d<4; d++){
                pair<int,int> nxt={i+dx[d],j+dy[d]};
                if(m[nxt.f][nxt.s]=='#') continue;
                e[i][j].push_back({nxt,1});
            }
        }
    }
}

void solve(int God){
    cin>>r>>c; pair<int,int> a,b;
    vector<pair<int,int>> wall;
    for(int i=1; i<=r; i++){
        for(int j=1; j<=c; j++) cin>>m[i][j];
    }
    for(int i=1; i<=r; i++){
        int pos=0;
        for(int j=1; j<=c; j++){
            if(m[i][j]!='#') le[i][j]=pos+1;
            else pos=j;
        }
        pos=c+1;
        for(int j=c; j>=1; j--){
            if(m[i][j]!='#') ri[i][j]=pos-1;
            else pos=j;
        }
    }
    for(int j=1; j<=c; j++){
        int pos=0;
        for(int i=1; i<=r; i++){
            if(m[i][j]!='#') up[i][j]=pos+1;
            else pos=i;
        }
        pos=r+1;
        for(int i=r; i>=1; i--){
            if(m[i][j]!='#') dn[i][j]=pos-1;
            else pos=i;
        }
    }
    for(int i=0; i<=r+1; i++){
        for(int j=0; j<=c+1; j++){
            if(m[i][j]=='#') wall.push_back({i,j});
            if(m[i][j]=='S') a={i,j};
            if(m[i][j]=='C') b={i,j};
        }
    }
    calc_dist_wall(wall);
    adds_edge();
    vector<vi> dist(r+2, vi(c+2,1e8));
    priority_queue<pair<int,pair<int,int>>> pq;
    pq.push({0,a});
    while(!pq.empty()){
        int cost=-pq.top().f; pair<int,int> cur=pq.top().s;
        pq.pop();
        if(dist[cur.f][cur.s]<cost) continue;
        for(const auto& to:e[cur.f][cur.s]){
            if(dist[to.f.f][to.f.s]>cost+to.s){
                dist[to.f.f][to.f.s]=cost+to.s;
                pq.push({-(cost+to.s),{to.f.f,to.f.s}});
            }
        }
    }
    cout<<dist[b.f][b.s];
}     
                       
signed main() {          
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int God=1; //cin>>God; 
    while (God--) {
        solve(God); nel;
    }
    return 0;
}

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