Submission #875307

#	Time	Username	Problem	Language	Result	Execution time	Memory
875307		irmuun	Portals (BOI14_portals)	C++17	100 / 100	498 ms	155912 KiB

portals

#include<bits/stdc++.h>

using namespace std;
 
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int r,c;
    cin>>r>>c;
    string s[r];
    int si,sj,ci,cj;
    for(int i=0;i<r;i++){
        cin>>s[i];
        for(int j=0;j<c;j++){
            if(s[i][j]=='S'){
                si=i;
                sj=j;
            }
            if(s[i][j]=='C'){
                ci=i;
                cj=j;
            }
        }
    }
    vector<array<int,3>>adj[r][c];
    int a[r][c][4];
    for(int i=0;i<r;i++){
        int cur=0;
        for(int j=0;j<c;j++){
            if(s[i][j]=='#'){
                cur=j+1;
            }
            else{
                a[i][j][0]=cur;
            }
        }
        cur=c-1;
        for(int j=c-1;j>=0;j--){
            if(s[i][j]=='#'){
                cur=j-1;
            }
            else{
                a[i][j][1]=cur;
            }
        }
    }
    for(int j=0;j<c;j++){
        int cur=0;
        for(int i=0;i<r;i++){
            if(s[i][j]=='#'){
                cur=i+1;
            }
            else{
                a[i][j][2]=cur;
            }
        }
        cur=r-1;
        for(int i=r-1;i>=0;i--){
            if(s[i][j]=='#'){
                cur=i-1;
            }
            else{
                a[i][j][3]=cur;
            }
        }
    }
    for(int i=0;i<r;i++){
        for(int j=0;j<c;j++){
            if(s[i][j]=='#') continue;
            if(i<r-1&&s[i][j]!='#'&&s[i+1][j]!='#'){
                adj[i][j].pb({i+1,j,1});
                adj[i+1][j].pb({i,j,1});
            }
            if(j<c-1&&s[i][j]!='#'&&s[i][j+1]!='#'){
                adj[i][j].pb({i,j+1,1});
                adj[i][j+1].pb({i,j,1});
            }
            int d=min({j-a[i][j][0],a[i][j][1]-j,i-a[i][j][2],a[i][j][3]-i})+1;
            adj[i][j].pb({i,a[i][j][0],d});
            adj[i][j].pb({i,a[i][j][1],d});
            adj[i][j].pb({a[i][j][2],j,d});
            adj[i][j].pb({a[i][j][3],j,d});
        }
    }
    vector<vector<int>>dist(r,vector<int>(c,1e9));
    set<array<int,3>>st;
    st.insert({0,si,sj});
    dist[si][sj]=0;
    while(!st.empty()){
        auto [d,i,j]=*st.begin();
        st.erase(st.begin());
        for(auto [x,y,w]:adj[i][j]){
            if(dist[i][j]+w<dist[x][y]){
                if(dist[x][y]<1e9){
                    st.erase({dist[x][y],x,y});
                }
                dist[x][y]=dist[i][j]+w;
                st.insert({dist[x][y],x,y});
            }
        }
    }
    cout<<dist[ci][cj];
}

Compilation message (stderr)

portals.cpp: In function 'int main()':
portals.cpp:94:16: warning: 'sj' may be used uninitialized in this function [-Wmaybe-uninitialized]
   94 |     dist[si][sj]=0;
      |                ^
portals.cpp:108:22: warning: 'cj' may be used uninitialized in this function [-Wmaybe-uninitialized]
  108 |     cout<<dist[ci][cj];
      |                      ^
portals.cpp:94:12: warning: 'si' may be used uninitialized in this function [-Wmaybe-uninitialized]
   94 |     dist[si][sj]=0;
      |            ^
portals.cpp:108:18: warning: 'ci' may be used uninitialized in this function [-Wmaybe-uninitialized]
  108 |     cout<<dist[ci][cj];
      |                  ^

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