Submission #418391

#	Time	Username	Problem	Language	Result	Execution time	Memory
418391		DJeniUp	Portals (BOI14_portals)	C++17	100 / 100	857 ms	162444 KiB

portals

#include <bits/stdc++.h>

using namespace std;

typedef int ll;
typedef pair<ll,ll>pairll;
typedef pair<ll,pairll>pairlll;
typedef pair<pairll,ll>pairllL;
typedef pair<pairll,pairll>pairllll;
typedef pair<ll,pairllll>pairlllll;
typedef long double ld;
typedef pair<ll,string>pairls;

#define endl '\n'
#define INF 100000000007
#define M 1000000000
#define P 316
#define MOD 998244353
#define pb push_back
#define fr first
#define sc second

ll n,m,d[1007][1007],a,b,t[1007][1007],f[1007][1007];
ll up[1007][1007],down[1007][1007],Left[1007][1007],Right[1007][1007];

char c;

vector<pairllL>v[1007][1007];

priority_queue<pairlll, vector<pairlll>, greater<pairlll> >q;

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>c;
            if(c=='.')d[i][j]=0;
            else if(c=='#')d[i][j]=1;
            else if(c=='C')d[i][j]=2;
            else if(c=='S')d[i][j]=3;
            t[i][j]=INF;
        }
    }
    for(int i=1;i<=n;i++){
        d[i][0]=1;
        d[i][m+1]=1;
    }
    for(int i=1;i<=m;i++){
        d[0][i]=1;
        d[n+1][i]=1;
    }
    ////////1
    for(int i=1;i<=n;i++){
        a=-1;
        for(int j=1;j<=m;j++){
            if(d[i][j]!=1){
                a++;
                Left[i][j]=a;
            }else{
                a=-1;
            }
        }
    }
    ////////2
    for(int i=1;i<=n;i++){
        a=-1;
        for(int j=m;j>=1;j--){
            if(d[i][j]!=1){
                a++;
                Right[i][j]=a;
            }else{
                a=-1;
                b=-1;
            }
        }
    }
    ////////3
    for(int j=1;j<=m;j++){
        a=-1;
        for(int i=1;i<=n;i++){
            if(d[i][j]!=1){
                a++;
                up[i][j]=a;
            }else{
                a=-1;
                b=-1;
            }
        }
    }
    ////////4
    for(int j=1;j<=m;j++){
        a=-1;
        for(int i=n;i>=1;i--){
            if(d[i][j]!=1){
                a++;
                down[i][j]=a;
            }else{
                a=-1;
                b=-1;
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(d[i][j]!=1){
                if(d[i+1][j]!=1){
                    v[i][j].pb({{i+1,j},1});
                }
                if(d[i-1][j]!=1){
                    v[i][j].pb({{i-1,j},1});
                }
                if(d[i][j+1]!=1){
                    v[i][j].pb({{i,j+1},1});
                }
                if(d[i][j-1]!=1){
                    v[i][j].pb({{i,j-1},1});
                }
                b=min(min(up[i][j],down[i][j]),min(Left[i][j],Right[i][j]));
                if(up[i][j]!=0)v[i][j].pb({{i-up[i][j],j},b+1});
                if(down[i][j]!=0)v[i][j].pb({{i+down[i][j],j},b+1});
                if(Left[i][j]!=0)v[i][j].pb({{i,j-Left[i][j]},b+1});
                if(Right[i][j]!=0)v[i][j].pb({{i,j+Right[i][j]},b+1});
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(d[i][j]==3){
                q.push({0,{i,j}});
                break;
            }
        }
    }
    while(q.size()>0){
        ll m1=q.top().fr;
        ll m2=q.top().sc.fr;
        ll m3=q.top().sc.sc;
        q.pop();
        if(f[m2][m3]==0){
            f[m2][m3]=1;
            t[m2][m3]=m1;
            for(int i=0;i<v[m2][m3].size();i++){
                a=v[m2][m3][i].fr.fr;
                b=v[m2][m3][i].fr.sc;
                ll h=v[m2][m3][i].sc;
                if(f[a][b]==0 && t[a][b]>m1+h){
                    t[a][b]=m1+h;
                    q.push({m1+h,{a,b}});
                }
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(d[i][j]==2){
                cout<<t[i][j]<<endl;
                return 0;
            }
        }
    }
    cout<<0<<endl;

    return 0;
}

Compilation message (stderr)

portals.cpp: In function 'int main()':
portals.cpp:15:13: warning: overflow in conversion from 'long int' to 'll' {aka 'int'} changes value from '100000000007' to '1215752199' [-Woverflow]
   15 | #define INF 100000000007
      |             ^~~~~~~~~~~~
portals.cpp:42:21: note: in expansion of macro 'INF'
   42 |             t[i][j]=INF;
      |                     ^~~
portals.cpp:143:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |             for(int i=0;i<v[m2][m3].size();i++){
      |                         ~^~~~~~~~~~~~~~~~~

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