Submission #129899

#	Time	Username	Problem	Language	Result	Execution time	Memory
129899		Abelyan	Portals (BOI14_portals)	C++17	100 / 100	197 ms	90872 KiB

portals

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
 
#define FOR(i,a) for (int i=0;i<(a);++i)
#define FORD(i,a) for (int i=(a)-1;i>=0;i--)
#define FORT(i,a,b) for (int i=(a);i<=(b);++i)
#define FORTD(i,b,a) for (int i=(b);i>=(a);--i)
#define trav(i,v) for (auto i : v)
#define all(v) v.begin(),v.end()
#define ad push_back
#define fr first
#define sc second
#define mpr(a,b) make_pair(a,b)
#define pir pair<int,int>
#define all(v) v.begin(),v.end()
#define make_unique(v) v.erase(unique(all(v)),v.end())
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define srng mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define y1 EsiHancagorcRepa
 
 
 
const int N=1e3+10;
const ll MOD=1e9+7;
 
int si,sj,ei,ej;
int l[N][N],r[N][N],u[N][N],d[N][N],dp[N][N];
char c[N][N];
bool col[N][N];
vector<pair<pir,int> > g[N][N];
vector<pir> pq[N*N];
 
class fastIO{
private:
    long long P10[19];
public:
    fastIO(){
        P10[0]=1;
        for (int i=1;i<=18;++i){
            P10[i]=P10[i-1]*10;
        }
    }
    long long read() {
        char ch=getchar();
        long long mul=1;
        if (ch=='-'){
            mul=-1;
            ch=getchar();
        }
        long long pat=0;
        while(ch==10 || ch==32)ch=getchar();
        while(ch>='0' && ch<='9'){
            pat=pat*10ll+(long long)(ch-'0');
            //cout<<ch<<endl;
            ch=getchar();
        }
        return pat*mul;
    }
    char readCh(){
        char ch=getchar();
        while(ch==10 || ch==32)ch=getchar();
        return ch;
    }
    void readStr(string &s){
        s="";
        char ch=getchar();
        while(ch==10 || ch==32)ch=getchar();
        while(ch!=10 && ch!=32){
            s+=ch;
            ch=getchar();
        }
 
    }
    void writeInt(int k,bool aft=false){
        if (k==0){
            putchar('0');
            putchar(32);
            return;
        }
        if (k<0){
            k=-k;
            putchar('-');
        }
        bool zro=false;
        for (int i=9;i>=0;--i){
            int tv=k/P10[i];
            k%=P10[i];
            if (tv==0 && !zro)continue;
            zro=true;
            putchar(tv+'0');
        }
        if (!aft) putchar(32);
    }
    void writeLL(long long k,bool aft=false){
        if (k==0){
            putchar('0');
            putchar(32);
            return;
        }
        if (k<0){
            k=-k;
            putchar('-');
        }
        bool zro=false;
        for (int i=18;i>=0;--i){
            int tv=k/P10[i];
            k%=P10[i];
            if (tv==0 && !zro)continue;
            zro=true;
            putchar(tv+'0');
        }
        if (!aft) putchar(32);
    }
    void writeStr(string &s,bool aft=false){
        int sz=s.length();
        for (int i=0;i<sz;++i){
            putchar(s[i]);
        }
        if (!aft) putchar(32);
    }
    void writechar(char k){
        putchar(k);
    }
    void space(){
        putchar(32);
    }
    void nwLn(){
        putchar(10);
    }
} io;
 
inline void upd(int x,int y,int x1,int y1,int her){
    if (!col[x1][y1]){
        if (dp[x1][y1]>dp[x][y]+her){
            dp[x1][y1]=dp[x][y]+her;
            pq[dp[x1][y1]].ad({x1,y1});
        }
    }
}
 
int main(){
    fastio;
    srng;
    int n=io.read(),m=io.read();
    FORT(i,1,n){
        FORT(j,1,m){
            c[i][j]=io.readCh();
            if (c[i][j]=='S'){
                si=i;
                sj=j;
                c[i][j]='.';
            }
            if (c[i][j]=='C'){
                ei=i;
                ej=j;
                c[i][j]='.';
            }
        }
    }
 
    FOR(i,n+2){
        c[i][m+1]='#';
        c[i][0]='#';
    }
    FOR(i,m+2){
        c[0][i]='#';
        c[n+1][i]='#';
    }
    //cout<<1<<endl;
    FORT(i,1,n){
        FORT(j,0,m+1){
            if (c[i][j]=='#'){
                l[i][j]=j;
            }
            else{
                l[i][j]=l[i][j-1];
            }
        }
        FORTD(j,m+1,0){
            if (c[i][j]=='#'){
                r[i][j]=j;
            }
            else{
                r[i][j]=r[i][j+1];
            }
        }
    }
    //cout<<2<<endl;
    FORT(j,1,m){
        FORT(i,0,n+1){
            if (c[i][j]=='#'){
                u[i][j]=i;
            }
            else{
                u[i][j]=u[i-1][j];
            }
        }
        FORTD(i,n+1,0){
            if (c[i][j]=='#'){
                d[i][j]=i;
            }
            else{
                d[i][j]=d[i+1][j];
            }
        }
    }
    //cout<<3<<endl;
    FORT(i,1,n){
        FORT(j,1,m){
            if (c[i][j]=='#')continue;
            dp[i][j]=INT_MAX;
        }
    }
    dp[si][sj]=0;
    pq[0].ad({si,sj});
    int ind=0,ind2=0;
    while(true){
        int x=-1,y=-1;
        do{
            //cout<<1<<endl;
            for (;ind2<pq[ind].size();++ind2){
                pir tv=pq[ind][ind2];
                if (!col[tv.fr][tv.sc]){
                    //cout<<"gta"<<endl;
                    x=tv.fr;
                    y=tv.sc;
                    break;
                }
            }
            if (x!=-1)break;
            ++ind;
            ind2=0;
        }while(ind<n*m);
        if (x==-1)break;
        //cout<<x<<" "<<y<<endl;
        if (x==ei && y==ej){
            io.writeInt(dp[x][y]);
            return 0;
        }
        col[x][y]=true;
        int her=min(min(y-l[x][y],r[x][y]-y),min(x-u[x][y],d[x][y]-x));
        if (c[x+1][y]=='.')
            upd(x,y,x+1,y,1);
        if (c[x-1][y]=='.')
            upd(x,y,x-1,y,1);
        if (c[x][y+1]=='.')
            upd(x,y,x,y+1,1);
        if (c[x][y-1]=='.')
            upd(x,y,x,y-1,1);
        upd(x,y,x,l[x][y]+1,her);
        upd(x,y,x,r[x][y]-1,her);
        upd(x,y,u[x][y]+1,y,her);
        upd(x,y,d[x][y]-1,y,her);
    }
    //cout<<dp[ei][ej]<<endl;
    return 0;
}

Compilation message (stderr)

portals.cpp: In function 'int main()':
portals.cpp:225:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (;ind2<pq[ind].size();++ind2){
                   ~~~~^~~~~~~~~~~~~~~

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