Submission #418329

#	Time	Username	Problem	Language	Result	Execution time	Memory
418329		DJeniUp	Portals (BOI14_portals)	C++17	20 / 100	38 ms	31488 KiB

portals

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll,ll>pairll;
typedef pair<ll,pairll>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 1000000000007
#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];

char c;

vector<pairll>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;
        b=-1;
        for(int j=1;j<=m;j++){
            if(d[i][j]!=1){
                if(a==-1){
                    a=i;
                    b=j;
                }
                if(d[i+1][j]==1 || d[i-1][j]==1 || d[i][j-1]==1 || d[i][j+1]==1){
                    v[i][j].pb({a,b});
                }
            }else{
                a=-1;
                b=-1;
            }
        }
    }
    ////////2
    for(int i=1;i<=n;i++){
        a=-1;
        b=-1;
        for(int j=m;j>=1;j--){
            if(d[i][j]!=1){
                if(a==-1){
                    a=i;
                    b=j;
                }
                if(d[i+1][j]==1 || d[i-1][j]==1 || d[i][j-1]==1 || d[i][j+1]==1){
                    v[i][j].pb({a,b});
                }
            }else{
                a=-1;
                b=-1;
            }
        }
    }
    ////////3
    for(int j=1;j<=m;j++){
        a=-1;
        b=-1;
        for(int i=1;i<=n;i++){
            if(d[i][j]!=1){
                if(a==-1){
                    a=i;
                    b=j;
                }
                if(d[i+1][j]==1 || d[i-1][j]==1 || d[i][j-1]==1 || d[i][j+1]==1){
                    v[i][j].pb({a,b});
                }
            }else{
                a=-1;
                b=-1;
            }
        }
    }
    ////////4
    for(int j=1;j<=m;j++){
        a=-1;
        b=-1;
        for(int i=n;i>=1;i--){
            if(d[i][j]!=1){
                if(a==-1){
                    a=i;
                    b=j;
                }
                if(d[i+1][j]==1 || d[i-1][j]==1 || d[i][j-1]==1 || d[i][j+1]==1){
                    v[i][j].pb({a,b});
                }
            }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});
                }
                if(d[i-1][j]!=1){
                    v[i][j].pb({i-1,j});
                }
                if(d[i][j+1]!=1){
                    v[i][j].pb({i,j+1});
                }
                if(d[i][j-1]!=1){
                    v[i][j].pb({i,j-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;
                b=v[m2][m3][i].sc;
                if(f[a][b]==0 && t[a][b]>m1+1){
                    t[a][b]=m1+1;
                    q.push({m1+1,{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:161:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  161 |             for(int i=0;i<v[m2][m3].size();i++){
      |                         ~^~~~~~~~~~~~~~~~~

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