Submission #1149601

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149601		12345678	Portals (BOI14_portals)	C++20	100 / 100	418 ms	178248 KiB

portals

#include <bits/stdc++.h>

using namespace std;

const int nx=1e3+5;

int n, m, dist[nx][nx], mn[nx][nx], vs[nx][nx], dx[]={1, 0, 0, -1}, dy[]={0, 1, -1, 0};
char mp[nx][nx];
string s;
vector<tuple<int, int, int>> d[nx][nx];
pair<int, int> st, ed, up[nx][nx], dn[nx][nx], l[nx][nx], r[nx][nx];
priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
queue<pair<int, int>> q;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    for (int i=0; i<=n+1; i++) for (int j=0; j<=m+1; j++) mp[i][j]='#';
    for (int i=1; i<=n; i++)
    {
        cin>>s;
        for (int j=1; j<=m; j++)
        {
            mp[i][j]=s[j-1];
            if (mp[i][j]=='S') mp[i][j]='.', st={i, j};
            if (mp[i][j]=='C') mp[i][j]='.', ed={i, j};
        }
    }
    for (int i=1; i<=n; i++)
    {
        for (int j=1; j<=m; j++)
        {
            if (mp[i][j]=='#') continue;
            if (mp[i][j-1]=='.') l[i][j]=l[i][j-1];
            else l[i][j]={i, j};
        }
        for (int j=m; j>=1; j--)
        {
            if (mp[i][j]=='#') continue;
            if (mp[i][j+1]=='.') r[i][j]=r[i][j+1];
            else r[i][j]={i, j};
        }
    }
    for (int j=1; j<=m; j++)
    {
        for (int i=1; i<=n; i++)
        {
            if (mp[i][j]=='#') continue;
            if (mp[i-1][j]=='.') up[i][j]=up[i-1][j];
            else up[i][j]={i, j};
        }
        for (int i=n; i>=1; i--)
        {
            if (mp[i][j]=='#') continue;
            if (mp[i+1][j]=='.') dn[i][j]=dn[i+1][j];
            else dn[i][j]={i, j};
        }
    }
    for (int i=1; i<=n; i++)
    {
        for (int j=1; j<=m; j++)
        {
            if (mp[i][j]=='#') continue;
            int cnt=0;
            for (int k=0; k<4; k++) if (mp[i+dx[k]][j+dy[k]]=='#') cnt++;
            if (cnt>0) q.push({i, j});
            else dist[i][j]=1e9;
        }
    }
    while (!q.empty())
    {
        auto [curi, curj]=q.front();
        q.pop();
        for (int k=0; k<4; k++)
        {
            int newi=curi+dx[k], newj=curj+dy[k];
            if (mp[newi][newj]=='.'&&dist[curi][curj]+1<dist[newi][newj]) dist[newi][newj]=dist[curi][curj]+1, q.push({newi, newj});
        }
    }
    for (int i=1; i<=n; i++)
    {
        for (int j=1; j<=m; j++)
        {
            if (mp[i][j]=='#') continue;
            for (int k=0; k<4; k++)
            {
                int newi=i+dx[k], newj=j+dy[k];
                if (mp[newi][newj]=='.') d[i][j].push_back({newi, newj, 1});
            }
            d[i][j].push_back({up[i][j].first, up[i][j].second, dist[i][j]+1});
            d[i][j].push_back({dn[i][j].first, dn[i][j].second, dist[i][j]+1});
            d[i][j].push_back({l[i][j].first, l[i][j].second, dist[i][j]+1});
            d[i][j].push_back({r[i][j].first, r[i][j].second, dist[i][j]+1});
        }
    }
    for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) mn[i][j]=1e9;
    mn[st.first][st.second]=0;
    pq.push({0, st.first, st.second});
    while (!pq.empty())
    {
        auto [cw, i, j]=pq.top();
        pq.pop();
        if (vs[i][j]) continue;
        vs[i][j]=1;
        //cout<<"dijk "<<i<<' '<<j<<' '<<cw<<'\n';
        for (auto [newi, newj, w]:d[i][j]) if (cw+w<mn[newi][newj]) mn[newi][newj]=cw+w, pq.push({cw+w, newi, newj});
    }
    cout<<mn[ed.first][ed.second];
}

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