Submission #1227722

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227722		thesen	Awesome Arrowland Adventure (eJOI19_adventure)	C++20	100 / 100	35 ms	10672 KiB

adventure

#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define vint vector <int>
#define vll vector <ll>
#define vbool vector<bool>
#define pairint pair<int,int>
#define pairll pair<ll,ll>
#define fi first
#define sc second
#define rever greater<ll>()
using namespace std;

ll n, m, res = -1;

struct dta{
    ll x, i, j;
};

void ins(vector<dta> &heap, dta a){
    if(a.i == n && a.j == m){
        if(res == -1){
            res = a.x;
        }else{
            res = min(res, a.x);
        }
    }
    heap.pb(a);
    ll ind = heap.size()-1;

    while(ind/2){
        if(heap[ind].x < heap[ind/2].x){
            swap(heap[ind], heap[ind/2]);
            ind/=2;
        }else{
            break;
        }
    }
}

void del(vector<dta> &heap){
    swap(heap[1], heap[heap.size()-1]);
    heap.pop_back();
    ll ind = 1;

    while(ind*2+1 < heap.size()){
        if(heap[ind*2].x < heap[ind*2+1].x){
            if(heap[ind*2].x < heap[ind].x){
                swap(heap[ind*2], heap[ind]);
                ind*=2;
            }else{
                break;
            }
        }else{
            if(heap[ind*2+1].x < heap[ind].x){
                swap(heap[ind*2+1], heap[ind]);
                ind*=2; ind++;
            }else{
                break;
            }
        }
    }
    if(ind*2 < heap.size()){
        if(heap[ind*2].x < heap[ind].x){
            swap(heap[ind*2], heap[ind]);
        }
    }
}

void func(ll n, vector<vbool> &noted, vector<dta> &heap, ll i, ll j, ll x){
    if(n == 0){
        i--;
    }else if(n == 1){
        j++;
    }else if(n == 2){
        i++;
    }else if(n == 3){
        j--;
    }//cout << i << ' ' << j << endl;

    if(noted[i][j]){
        return;
    }
    ins(heap, {x, i, j});
}


void dfs(vector<vll> &mp, vector<vbool> &noted, vector<dta> &heap, vector<vll> &dp, ll i, ll j){
    noted[i][j] = true; //cout << i << ' ' << j << endl;
    if(mp[i][j] == 10){
        return;
    }
    for(int k = 1; k <= 3; k++){
        func((mp[i][j]+k)%4, noted, heap, i, j, dp[i][j]+k);
    }
    ll depe = dp[i][j];
    if(mp[i][j] == 0){
        i--;
    }else if(mp[i][j] == 1){
        j++;
    }else if(mp[i][j] == 2){
        i++;
    }else if(mp[i][j] == 3){
        j--;
    }
    if(noted[i][j]){
        return;
    }
    dp[i][j] = depe;
    if(i == n && j == m){
        if(res == -1){
            res = depe;
        }else{
            res = min(res, depe);
        }
    }
    dfs(mp, noted, heap, dp, i, j);
}

void solve(ll tc){
    cin >> n >> m;

    vector<vll> mp(n+2, vll(m+2, -1)), dp(n+2, vll(m+2, -1));
    vector<vbool> noted(n+2, vbool(m+2, true));
    string s;
    for(int i = 1; i <= n; i++){
        cin >> s; s = '1' + s;
        for(int j = 1; j <= m; j++){
            if(s[j] == 'N'){
                mp[i][j] = 0;
            }else if(s[j] == 'E'){
                mp[i][j] = 1;
            }else if(s[j] == 'S'){
                mp[i][j] = 2;
            }else if(s[j] == 'W'){
                mp[i][j] = 3;
            }else{
                mp[i][j] = 10;
            }
            noted[i][j] = false;
        }
    }
    if(n == 1 && m == 1){
        cout << 0 << endl; return;
    }

    vector<dta> heap(1);
    heap.pb({0, 1, 1});
    while(heap.size() > 1){
        if(noted[heap[1].i][heap[1].j]){
            del(heap);
            continue;
        } //cout << 0;
        dp[heap[1].i][heap[1].j] = heap[1].x;
        dfs(mp, noted, heap, dp, heap[1].i, heap[1].j);
        del(heap);
        if(res != -1){
            cout << res << endl; return;
        }
    }
    cout << -1 << endl;
}

int main(){
    ll t; t = 1;
    for(int i = 1; i <= t; i++){
        solve(i);
    }
}

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