oj.uz

Submission #282733

# Submission time Handle Problem Language Result Execution time Memory
282733 2020-08-24T19:44:34 Z mosiashvililuka Awesome Arrowland Adventure (eJOI19_adventure) C++17
0 / 100
 9 ms 12160 KB 
#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];
pair <int, int> pr[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*(a+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]));
    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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 12160 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 12160 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12160 KB Output is correct
2 Correct 8 ms 12160 KB Output is correct
3 Incorrect 8 ms 12160 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 12160 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 12160 KB Output isn't correct
2 Halted 0 ms 0 KB -