Submission #282747

#	Time	Username	Problem	Language	Result	Execution time	Memory
282747		mosiashvililuka	Awesome Arrowland Adventure (eJOI19_adventure)	C++14	100 / 100	133 ms	28524 KiB

adventure

#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,id[509][509],bo[500009];
string ss[509];
vector <pair <int, int> > v[500009];
map <char, int> m;
priority_queue <pair <int, int> > s;
void chk(int q, int w){
    if(q<0||q>a||w<0||w>b) return;
    int qw=0,we=0;
    if(q==i-1) we=1;
    if(w==j+1) we=2;
    if(q==i+1) we=3;
    if(w==j-1) we=4;
    if(we>=m[ss[i][j]]){
        qw=we-m[ss[i][j]];
    }else{
        qw=4+we-m[ss[i][j]];
    }
    v[id[i][j]].push_back(make_pair(id[q][w],qw));
}
int main(){
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>a>>b;
    for(i=1; i<=a; i++){
        cin>>ss[i];
        ss[i].insert(0,"0");
    }
    m['N']=1;m['E']=2;m['S']=3;m['W']=4;
    for(i=1; i<=a; i++) for(j=1; j<=b; j++){
        id[i][j]=i*(b+2)+j;
        /*pr[id[i][j]].first=i;
        pr[id[i][j]].second=j;*/
    }
    for(i=1; i<=a; i++){
        for(j=1; j<=b; j++){
            if(ss[i][j]=='X') continue;
            chk(i-1,j);
            chk(i+1,j);
            chk(i,j-1);
            chk(i,j+1);
        }
    }
    s.push(make_pair(0,id[1][1]));
    zx=-1;
    while(s.size()){
        while(s.size()&&bo[s.top().second]==1) s.pop();
        if(s.size()==0) break;
        c=s.top().second;d=s.top().first;
        //cout<<pr[c].first<<" "<<pr[c].second<<"   "<<d<<endl;
        if(c==id[a][b]){
            zx=-d;
            break;
        }
        s.pop();
        bo[c]=1;
        for(vector <pair <int, int> >::iterator it=v[c].begin(); it!=v[c].end(); it++){
            if(bo[(*it).first]==1) continue;
            s.push(make_pair(d-(*it).second,(*it).first));
        }
    }
    cout<<zx;
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 16 / 16
• Subtask 5: 50 / 50