oj.uz

Submission #129899

# Submission time Handle Problem Language Result Execution time Memory
129899 2019-07-13T13:26:55 Z Abelyan Portals (BOI14_portals) C++17
100 / 100
 197 ms 90872 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 48376 KB Output is correct
2 Correct 46 ms 48632 KB Output is correct
3 Correct 46 ms 48504 KB Output is correct
4 Correct 46 ms 48488 KB Output is correct
5 Correct 46 ms 48504 KB Output is correct
6 Correct 46 ms 48504 KB Output is correct
7 Correct 46 ms 48504 KB Output is correct
8 Correct 47 ms 48504 KB Output is correct
9 Correct 47 ms 48364 KB Output is correct
10 Correct 46 ms 48376 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 48248 KB Output is correct
2 Correct 46 ms 48592 KB Output is correct
3 Correct 46 ms 48504 KB Output is correct
4 Correct 46 ms 48376 KB Output is correct
5 Correct 46 ms 48504 KB Output is correct
6 Correct 46 ms 48504 KB Output is correct
7 Correct 46 ms 48504 KB Output is correct
8 Correct 46 ms 48504 KB Output is correct
9 Correct 60 ms 49372 KB Output is correct
10 Correct 47 ms 49400 KB Output is correct
11 Correct 47 ms 49400 KB Output is correct
12 Correct 48 ms 49400 KB Output is correct
13 Correct 47 ms 49400 KB Output is correct
14 Correct 45 ms 48376 KB Output is correct
15 Correct 47 ms 49388 KB Output is correct
16 Correct 46 ms 48376 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 48372 KB Output is correct
2 Correct 47 ms 48504 KB Output is correct
3 Correct 46 ms 48480 KB Output is correct
4 Correct 46 ms 48504 KB Output is correct
5 Correct 54 ms 52904 KB Output is correct
6 Correct 54 ms 52984 KB Output is correct
7 Correct 63 ms 52860 KB Output is correct
8 Correct 54 ms 53496 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 48380 KB Output is correct
2 Correct 46 ms 48560 KB Output is correct
3 Correct 46 ms 48528 KB Output is correct
4 Correct 46 ms 48380 KB Output is correct
5 Correct 58 ms 48504 KB Output is correct
6 Correct 47 ms 48508 KB Output is correct
7 Correct 46 ms 48504 KB Output is correct
8 Correct 46 ms 48504 KB Output is correct
9 Correct 47 ms 49400 KB Output is correct
10 Correct 48 ms 49400 KB Output is correct
11 Correct 47 ms 49456 KB Output is correct
12 Correct 47 ms 49400 KB Output is correct
13 Correct 47 ms 49400 KB Output is correct
14 Correct 55 ms 52988 KB Output is correct
15 Correct 54 ms 52864 KB Output is correct
16 Correct 53 ms 52856 KB Output is correct
17 Correct 54 ms 52856 KB Output is correct
18 Correct 56 ms 52920 KB Output is correct
19 Correct 51 ms 52604 KB Output is correct
20 Correct 53 ms 53000 KB Output is correct
21 Correct 54 ms 52984 KB Output is correct
22 Correct 53 ms 52856 KB Output is correct
23 Correct 53 ms 52856 KB Output is correct
24 Correct 53 ms 53112 KB Output is correct
25 Correct 46 ms 48376 KB Output is correct
26 Correct 47 ms 49400 KB Output is correct
27 Correct 46 ms 48352 KB Output is correct
28 Correct 54 ms 53624 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 48248 KB Output is correct
2 Correct 47 ms 48504 KB Output is correct
3 Correct 46 ms 48504 KB Output is correct
4 Correct 47 ms 48504 KB Output is correct
5 Correct 47 ms 48504 KB Output is correct
6 Correct 47 ms 48504 KB Output is correct
7 Correct 46 ms 48504 KB Output is correct
8 Correct 46 ms 48504 KB Output is correct
9 Correct 47 ms 49400 KB Output is correct
10 Correct 47 ms 49400 KB Output is correct
11 Correct 47 ms 49400 KB Output is correct
12 Correct 48 ms 49400 KB Output is correct
13 Correct 48 ms 49400 KB Output is correct
14 Correct 55 ms 52984 KB Output is correct
15 Correct 54 ms 52984 KB Output is correct
16 Correct 53 ms 52856 KB Output is correct
17 Correct 54 ms 53064 KB Output is correct
18 Correct 54 ms 52984 KB Output is correct
19 Correct 51 ms 52516 KB Output is correct
20 Correct 51 ms 52984 KB Output is correct
21 Correct 54 ms 53112 KB Output is correct
22 Correct 54 ms 52988 KB Output is correct
23 Correct 53 ms 52900 KB Output is correct
24 Correct 184 ms 77020 KB Output is correct
25 Correct 190 ms 78204 KB Output is correct
26 Correct 108 ms 70476 KB Output is correct
27 Correct 151 ms 75284 KB Output is correct
28 Correct 194 ms 77464 KB Output is correct
29 Correct 188 ms 76920 KB Output is correct
30 Correct 174 ms 75240 KB Output is correct
31 Correct 53 ms 53176 KB Output is correct
32 Correct 197 ms 80112 KB Output is correct
33 Correct 46 ms 48376 KB Output is correct
34 Correct 47 ms 49400 KB Output is correct
35 Correct 149 ms 74772 KB Output is correct
36 Correct 47 ms 48472 KB Output is correct
37 Correct 53 ms 53496 KB Output is correct
38 Correct 188 ms 90872 KB Output is correct
39 Correct 141 ms 73524 KB Output is correct