oj.uz

Submission #232170

# Submission time Handle Problem Language Result Execution time Memory
232170 2020-05-16T10:27:31 Z Dremix10 Awesome Arrowland Adventure (eJOI19_adventure) C++17
34 / 100
 10 ms 7296 KB 
#include <bits/stdc++.h>
using namespace std;

struct ano{

int c;
int d;

bool operator<(const ano &o)const{
return d>o.d;
}

};

int main (){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

int n,m;
cin>>n>>m;

vector<vector<ano> > a(250000,vector<ano>());
priority_queue<ano> q;
vector <int> d(250000,1000000);
vector <bool> v(250000,0);

int i,j;
char c;
for(i=0;i<n;i++)
for(j=0;j<m;j++){

    cin>>c;

    if(c=='X')
        continue;

    if(c=='N'){
        if(i-1>=0)
            a[i*m+j].push_back({(i-1)*m+j,0});
        if(j+1<m)
            a[i*m+j].push_back({i*m+j+1,1});
        if(i+1<n)
            a[i*m+j].push_back({(i+1)*m+j,2});
        if(j-1>=0)
            a[i*m+j].push_back({i*m+j-1,3});
    }
    else if(c=='E'){
        if(i-1>=0)
            a[i*m+j].push_back({(i-1)*m+j,3});
        if(j+1<m)
            a[i*m+j].push_back({i*m+j+1,0});
        if(i+1<n)
            a[i*m+j].push_back({(i+1)*m+j,1});
        if(j-1>=0)
            a[i*m+j].push_back({i*m+j-1,2});
    }
    else if(c=='S'){
        if(i-1>=0)
            a[i*m+j].push_back({(i-1)*m+j,2});
        if(j+1<m)
            a[i*m+j].push_back({i*m+j+1,3});
        if(i+1<n)
            a[i*m+j].push_back({(i+1)*m+j,0});
        if(j-1>=0)
            a[i*m+j].push_back({i*m+j-1,1});
    }
    else{
        if(i-1>=0)
            a[i*m+j].push_back({(i-1)*m+j,1});
        if(j+1<m)
            a[i*m+j].push_back({i*m+j+1,2});
        if(i+1<n)
            a[i*m+j].push_back({(i+1)*m+j,3});
        if(j-1>=0)
            a[i*m+j].push_back({i*m+j-1,0});
    }

}


q.push({0,0});
d[0]=0;

int start,w;

while(!q.empty()){
    start=q.top().c;
    w=q.top().d;
    q.pop();

    if(d[start]<w)
        continue;

    if(v[start])
        continue;

    v[start]=1;

    for(auto x : a[start])
    if(d[x.c]>d[start]+x.d){
        d[x.c]=d[start]+x.d;
        q.push(x);
    }

}

if(d[n*m-1]==1000000)
    cout<<-1<<endl;
else
    cout<<d[n*m-1]<<endl;


}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7296 KB Output is correct
2 Correct 9 ms 7168 KB Output is correct
3 Correct 8 ms 7296 KB Output is correct
4 Correct 9 ms 7296 KB Output is correct
5 Correct 9 ms 7296 KB Output is correct
6 Correct 9 ms 7168 KB Output is correct
7 Correct 9 ms 7168 KB Output is correct
8 Correct 8 ms 7168 KB Output is correct
9 Correct 9 ms 7296 KB Output is correct
10 Correct 9 ms 7296 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7296 KB Output is correct
2 Correct 9 ms 7168 KB Output is correct
3 Correct 8 ms 7296 KB Output is correct
4 Correct 9 ms 7296 KB Output is correct
5 Correct 9 ms 7296 KB Output is correct
6 Correct 9 ms 7168 KB Output is correct
7 Correct 9 ms 7168 KB Output is correct
8 Correct 8 ms 7168 KB Output is correct
9 Correct 9 ms 7296 KB Output is correct
10 Correct 9 ms 7296 KB Output is correct
11 Correct 9 ms 7168 KB Output is correct
12 Correct 9 ms 7296 KB Output is correct
13 Correct 9 ms 7296 KB Output is correct
14 Correct 9 ms 7168 KB Output is correct
15 Correct 9 ms 7296 KB Output is correct
16 Correct 9 ms 7168 KB Output is correct
17 Correct 10 ms 7296 KB Output is correct
18 Correct 9 ms 7296 KB Output is correct
19 Correct 8 ms 7296 KB Output is correct
20 Correct 9 ms 7296 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7168 KB Output is correct
2 Correct 9 ms 7296 KB Output is correct
3 Correct 9 ms 7168 KB Output is correct
4 Correct 9 ms 7296 KB Output is correct

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7296 KB Output is correct
2 Incorrect 10 ms 7168 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7296 KB Output is correct
2 Correct 9 ms 7168 KB Output is correct
3 Correct 8 ms 7296 KB Output is correct
4 Correct 9 ms 7296 KB Output is correct
5 Correct 9 ms 7296 KB Output is correct
6 Correct 9 ms 7168 KB Output is correct
7 Correct 9 ms 7168 KB Output is correct
8 Correct 8 ms 7168 KB Output is correct
9 Correct 9 ms 7296 KB Output is correct
10 Correct 9 ms 7296 KB Output is correct
11 Correct 9 ms 7168 KB Output is correct
12 Correct 9 ms 7296 KB Output is correct
13 Correct 9 ms 7296 KB Output is correct
14 Correct 9 ms 7168 KB Output is correct
15 Correct 9 ms 7296 KB Output is correct
16 Correct 9 ms 7168 KB Output is correct
17 Correct 10 ms 7296 KB Output is correct
18 Correct 9 ms 7296 KB Output is correct
19 Correct 8 ms 7296 KB Output is correct
20 Correct 9 ms 7296 KB Output is correct
21 Correct 9 ms 7168 KB Output is correct
22 Correct 9 ms 7296 KB Output is correct
23 Correct 9 ms 7168 KB Output is correct
24 Correct 9 ms 7296 KB Output is correct
25 Correct 10 ms 7296 KB Output is correct
26 Incorrect 10 ms 7168 KB Output isn't correct
27 Halted 0 ms 0 KB -