Submission #1057217

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057217		NemanjaSo2005	Portals (BOI14_portals)	C++17	100 / 100	356 ms	123228 KiB

portals

#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")

using namespace std;

void solve(){
    int n, m;cin>>n>>m;n+=2;m+=2;
    vector<vector<char>> v(n, vector<char>(m, '#'));
    int s = -1, c = -1;
    for(int i = 1;i<n-1;i++){
        for(int j = 1;j<m-1;j++){
            cin>>v[i][j];
            if(v[i][j]=='S') s = i*m+j;
            if(v[i][j]=='C') c = i*m+j;
        }
    }
    vector<vector<pair<int, int>>> e(n*m);
    vector<int> levo(n*m), desno(n*m), gore(n*m), dole(n*m);
    for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++){
            if(v[i][j]=='#'){
                levo[i*m+j] = j;
                gore[i*m+j] = i;
            } else{
                levo[i*m+j] = levo[i*m+j-1];
                gore[i*m+j] = gore[(i-1)*m+j];
            }
        }
    }
    for(int i = n-1;i>=0;i--){
        for(int j = m-1;j>=0;j--){
            if(v[i][j]=='#'){
                desno[i*m+j] = j;
                dole[i*m+j] = i;
            } else{
                desno[i*m+j] = desno[i*m+j+1];
                dole[i*m+j] = dole[(i+1)*m+j];
            }
        }
    }
    for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++){
            if(v[i][j]=='#') continue;
            e[i*m+j].push_back({(i-1)*m+j, 1});
            e[i*m+j].push_back({i*m+j+1, 1});
            e[i*m+j].push_back({(i+1)*m+j, 1});
            e[i*m+j].push_back({i*m+j-1, 1});
            int ii = dole[i*m+j], iii = gore[i*m+j], jj = desno[i*m+j], jjj = levo[i*m+j];
            int x = min(min(ii-i, i-iii), min(jj-j, j-jjj));
            ii--;
            iii++;
            jj--;
            jjj++;
            e[i*m+j].push_back({ii*m+j, x});
            e[i*m+j].push_back({iii*m+j, x});
            e[i*m+j].push_back({i*m+jj, x});
            e[i*m+j].push_back({i*m+jjj, x});
        }
    }
    priority_queue<pair<int, int>> q;
    vector<int> d(n*m, 1'000'000'000);
    d[s] = 0;
    q.push({-d[s], s});
    while(!q.empty()){
        int u = q.top().second;
        q.pop();
        for(int i = 0;i<e[u].size();i++){
            int v = e[u][i].first;
            if(d[u]+e[u][i].second<d[v]){
                d[v] = d[u]+e[u][i].second;
                q.push({-d[v], v});
            }
        }
    }
    cout<<d[c]<<endl;
    return;
}

int32_t main(){
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(false);
    int t = 1;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

Compilation message (stderr)

portals.cpp: In function 'void solve()':
portals.cpp:68:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         for(int i = 0;i<e[u].size();i++){
      |                       ~^~~~~~~~~~~~

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