oj.uz

Submission #999772

# Submission time Handle Problem Language Result Execution time Memory
999772 2024-06-16T06:40:19 Z vjudge1 Awesome Arrowland Adventure (eJOI19_adventure) C++14
34 / 100
 53 ms 11940 KB 
/*       ==========================
        | Bismillahirrahmanirrahim | ⠀⠀ 
         ==========================
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠸⠁⠸⢳⡄⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⠃⠀⠀⢸⠸⠀⡠⣄⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡠⠃⠀⠀⢠⣞⣀⡿⠀⠀⣧⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣠⡖⠁⠀⠀⠀⢸⠈⢈⡇⠀⢀⡏⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⡴⠩⢠⡴⠀⠀⠀⠀⠀⠈⡶⠉⠀⠀⡸⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⢀⠎⢠⣇⠏⠀⠀⠀⠀⠀⠀⠀⠁⠀⢀⠄⡇⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢠⠏⠀⢸⣿⣴⠀⠀⠀⠀⠀⠀⣆⣀⢾⢟⠴⡇⠀⠀⠀⠀⠀<===== this is wolf, not everest
⠀⠀⠀⠀⠀⢀⣿⠀⠠⣄⠸⢹⣦⠀⠀⡄⠀⠀⢋⡟⠀⠀⠁⣇⠀⠀⠀⠀⠀
⠀⠀⠀⠀⢀⡾⠁⢠⠀⣿⠃⠘⢹⣦⢠⣼⠀⠀⠉⠀⠀⠀⠀⢸⡀⠀⠀⠀⠀
⠀⠀⢀⣴⠫⠤⣶⣿⢀⡏⠀⠀⠘⢸⡟⠋⠀⠀⠀⠀⠀⠀⠀⠀⢳⠀⠀⠀⠀
⠐⠿⢿⣿⣤⣴⣿⣣⢾⡄⠀⠀⠀⠀⠳⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢣⠀⠀⠀
⠀⠀⠀⣨⣟⡍⠉⠚⠹⣇⡄⠀⠀⠀⠀⠀⠀⠀⠀⠈⢦⠀⠀⢀⡀⣾⡇⠀⠀
⠀⠀⢠⠟⣹⣧⠃⠀⠀⢿⢻⡀⢄⠀⠀⠀⠀⠐⣦⡀⣸⣆⠀⣾⣧⣯⢻⠀⠀
⠀⠀⠘⣰⣿⣿⡄⡆⠀⠀⠀⠳⣼⢦⡘⣄⠀⠀⡟⡷⠃⠘⢶⣿⡎⠻⣆⠀⠀
⠀⠀⠀⡟⡿⢿⡿⠀⠀⠀⠀⠀⠙⠀⠻⢯⢷⣼⠁⠁⠀⠀⠀⠙⢿⡄⡈⢆⠀
⠀⠀⠀⠀⡇⣿⡅⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠦⠀⠀⠀⠀⠀⠀⡇⢹⢿⡀
⠀⠀⠀⠀⠁⠛⠓⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠼⠇⠁ 

m : 11059739 -> l ~23
p : 4567896467
*/
#pragma GCC optimize("O3", "inline")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define all(v) v.begin(), v.end()
#define ins insert
#define pb push_back
#define int long long int
#define pii pair<int, int>
#define str string
#define endl '\n'
#define drop(x) cout<<(x)<<endl;return;
// mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <class T> using ot = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int mod = 998244353, sze =8*1e5 + 10, inf = 1e9, prime = 4567896467;

int cost[500][500];
char arr[500][500];
int yc[sze];

int cc(char a,char b){
    if(yc[a]<=yc[b]){
        return yc[b]-yc[a];
    }
    return 4 - yc[a] + yc[b];
}
int n,m;
vector<char> yonler;
int used[500][500];
void dfs(int x,int y,int c=0){
    used[x][y]++;
    if(x==n-1 && y==m-1){
        if(cost[x][y]==-1){
            cost[x][y]=inf;
        }
        cost[x][y]=min(cost[x][y],c);

        return;
    }
    if(arr[x][y]=='X' || (x>=n || y>=m || x<0 || y<0 || used[x][y]>10000 )|| ( cost[x][y]!=-1 && c>cost[x][y])){
        return;
    }
    // cout<<x<<" "<<y<<endl;
    if(cost[x][y]==-1){
        cost[x][y]=inf;
    }
    cost[x][y]=min(cost[x][y],c);
    
    for(auto v:yonler){
        if(v=='N'){
            dfs(x-1,y,c + cc(arr[x][y],v));
        }
        else if(v=='E'){
            dfs(x,y+1,c + cc(arr[x][y],v));
        }
        else if(v=='S'){
            dfs(x+1,y,c + cc(arr[x][y],v));
        }
        else if(v=='W'){
            dfs(x,y-1,c + cc(arr[x][y],v));
        }
    }
    // WNES
}
void mal(){
    cin>>n>>m;
    yonler={'N','E','S','W'};
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>arr[i][j];
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cost[i][j]=-1;
        }
    }
    cost[0][0]=0;
    cost[n-1][m-1]=-1;

    yc['N']=0;
    yc['E']=1;
    yc['S']=2;
    yc['W']=3;

    if(m==2){
        if(arr[0][0]=='X'){
            drop(-1);
        }
        cost[0][1] = cc(arr[0][0],'E');
        // cout<<cost[0][0]<<" "<<cost[0][1]<<endl;
        for(int i=1;i<n;i++){
            
            if(arr[i][0]!='X' || (0==m-1 && i==n-1)){
                if(cost[i-1][0]!=-1){
                    cost[i][0] = cost[i-1][0] + cc(arr[i-1][0],'S');    
                    // cout<<"sa:"<<i<<" " <<cost[i][0]<<endl;
                }
                if(cost[i-1][1]!=-1 && arr[i][1]!='X'){
                    if(cost[i][0]==-1){
                        cost[i][0]=inf;
                    }
                    cost[i][0]= min(cost[i][0], cost[i-1][1] + cc(arr[i-1][1],'S') + cc(arr[i][1],'W'));
                }
            }
            if(arr[i][1]!='X' || (1==m-1 && i==n-1)){
                // cout<<i<<" "<<1<<endl;
                if(cost[i-1][1]!=-1){
                    cost[i][1] = cost[i-1][1] + cc(arr[i-1][1],'S');    
                }

                if(cost[i-1][0]!=-1 && arr[i][0]!='X'){
                    if(cost[i][1]==-1){
                        cost[i][1]=inf;
                    }
                    cost[i][1]=min(cost[i][1],cost[i-1][0] + cc(arr[i-1][0],'S') + cc(arr[i][0],'E'));
                }
            }
            // cout<<i<<" "<<cost[i][0]<<" "<<cost[i][1]<<endl;
        
        }



        drop(cost[n-1][m-1]);
        return;
    }
    dfs(0,0);
    drop(cost[n-1][m-1]);
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int tt = 1;
    // cin>>tt;

    while (tt--) mal();
}

Compilation message

adventure.cpp: In function 'long long int cc(char, char)':
adventure.cpp:49:11: warning: array subscript has type 'char' [-Wchar-subscripts]
   49 |     if(yc[a]<=yc[b]){
      |           ^
adventure.cpp:49:18: warning: array subscript has type 'char' [-Wchar-subscripts]
   49 |     if(yc[a]<=yc[b]){
      |                  ^
adventure.cpp:50:19: warning: array subscript has type 'char' [-Wchar-subscripts]
   50 |         return yc[b]-yc[a];
      |                   ^
adventure.cpp:50:25: warning: array subscript has type 'char' [-Wchar-subscripts]
   50 |         return yc[b]-yc[a];
      |                         ^
adventure.cpp:52:19: warning: array subscript has type 'char' [-Wchar-subscripts]
   52 |     return 4 - yc[a] + yc[b];
      |                   ^
adventure.cpp:52:27: warning: array subscript has type 'char' [-Wchar-subscripts]
   52 |     return 4 - yc[a] + yc[b];
      |                           ^

Subtask #1
10.0 / 10.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 0 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 36 ms 4956 KB Output is correct
13 Correct 53 ms 5464 KB Output is correct
14 Correct 1 ms 4956 KB Output is correct
15 Correct 18 ms 5420 KB Output is correct
16 Correct 39 ms 5212 KB Output is correct
17 Correct 41 ms 5456 KB Output is correct
18 Correct 12 ms 5468 KB Output is correct
19 Correct 19 ms 4956 KB Output is correct
20 Correct 51 ms 5208 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 2 ms 4952 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5724 KB Output is correct
2 Incorrect 11 ms 11940 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 0 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 36 ms 4956 KB Output is correct
13 Correct 53 ms 5464 KB Output is correct
14 Correct 1 ms 4956 KB Output is correct
15 Correct 18 ms 5420 KB Output is correct
16 Correct 39 ms 5212 KB Output is correct
17 Correct 41 ms 5456 KB Output is correct
18 Correct 12 ms 5468 KB Output is correct
19 Correct 19 ms 4956 KB Output is correct
20 Correct 51 ms 5208 KB Output is correct
21 Correct 1 ms 4440 KB Output is correct
22 Correct 2 ms 4952 KB Output is correct
23 Correct 1 ms 4444 KB Output is correct
24 Correct 1 ms 4444 KB Output is correct
25 Correct 3 ms 5724 KB Output is correct
26 Incorrect 11 ms 11940 KB Output isn't correct
27 Halted 0 ms 0 KB -