Submission #465771

#	Time	Username	Problem	Language	Result	Execution time	Memory
465771		MohamedFaresNebili	Portals (BOI14_portals)	C++14	100 / 100	638 ms	52292 KiB

portals

#include <bits/stdc++.h>

using namespace std;

void solve()
{
    const int nx[4] = {0, 0, 1, -1}, ny[4] = {1, -1, 0, 0};
    int n, m; cin>>n>>m; char grid[n][m];
    int sx, sy, ex, ey; int d[n][m]; set<int>h[m], v[n];
    for(int l=0;l<m;l++) {
        h[l].insert(-1); h[l].insert(n);
    }
    for(int l=0;l<n;l++) {
        v[l].insert(-1); v[l].insert(m);
    }
    for(int l=0;l<n;l++) {
        for(int i=0;i<m;i++) {
            cin>>grid[l][i]; d[l][i]=1000000000;
            if(grid[l][i]=='S') { sx=l; sy=i; d[l][i]=0; }
            if(grid[l][i]=='C') { ex=l; ey=i; }
            if(grid[l][i]=='#') {
                h[i].insert(l);
                v[l].insert(i);
            }
        }
    }
    priority_queue<pair<int, pair<int, int>>>pq; pq.push({0, {sx, sy}});
    while(!pq.empty()) {
        int a=pq.top().second.first, b=pq.top().second.second, w=-pq.top().first; pq.pop();
        if(a==ex&&b==ey) { cout<<w<<'\n'; return; }
      	if(d[a][b]<w) continue;
        for(int l=0;l<4;l++) {
            int x=a+nx[l], y=b+ny[l];
            if(x<0||x>=n||y<0||y>=m||grid[x][y]=='#') continue;
            if(d[x][y]>d[a][b]+1) {
                d[x][y]=d[a][b]+1; pq.push({-d[x][y], {x, y}});
            }
        }
        auto i=h[b].lower_bound(a), j=h[b].upper_bound(a), u=v[a].lower_bound(b), k=v[a].upper_bound(b); i--; u--;
        int p=min({*j-a, a-*i, *k-b, b-*u});
        int a1=*i+1, aa=*j-1, b1=*u+1, bb=*k-1;
        if(a1>=0&&a1<n&&grid[a1][b]!='#') {
            if(d[a1][b]>d[a][b]+p) {
                d[a1][b]=d[a][b]+p;
                pq.push({-d[a1][b], {a1, b}});
            }
        }
        if(aa>=0&&aa<n&&grid[aa][b]!='#') {
            if(d[aa][b]>d[a][b]+p) {
                d[aa][b]=d[a][b]+p;
                pq.push({-d[aa][b], {aa, b}});
            }
        }
        if(b1>=0&&b1<m&&grid[a][b1]!='#') {
            if(d[a][b1]>d[a][b]+p) {
                d[a][b1]=d[a][b]+p;
                pq.push({-d[a][b1], {a, b1}});
            }
        }
        if(bb>=0&&bb<m&&grid[a][bb]!='#') {
            if(d[a][bb]>d[a][b]+p) {
                d[a][bb]=d[a][b]+p;
                pq.push({-d[a][bb], {a, bb}});
            }
        }
    }
}

int main()
{
    int t; t=1;
    while(t--) {
        solve();
    }
}

Compilation message (stderr)

portals.cpp: In function 'void solve()':
portals.cpp:30:9: warning: 'ex' may be used uninitialized in this function [-Wmaybe-uninitialized]
   30 |         if(a==ex&&b==ey) { cout<<w<<'\n'; return; }
      |         ^~
portals.cpp:30:17: warning: 'ey' may be used uninitialized in this function [-Wmaybe-uninitialized]
   30 |         if(a==ex&&b==ey) { cout<<w<<'\n'; return; }
      |            ~~~~~^~~~~~~

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