Submission #965532

#	Time	Username	Problem	Language	Result	Execution time	Memory
965532		efedmrlr	Soccer (JOI17_soccer)	C++17	100 / 100	686 ms	39100 KiB

soccer

// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>

using namespace std;


#define lli long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()


void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}


const double EPS = 0.00001;
const lli INF = 1e18;
const int N = 3e5+5;
const int ALPH = 26;
const int LGN = 25;
constexpr int MOD = 1e9+7;
int h, w, n;
int A, B, C;

array<array<int, 2>, 5> dir;
// 1 down, 2 up, 3 right, 4 left

array<int,2> s, t;
vector<vector<lli> > gr;

void bfs() {
    queue<array<lli,2> > que;
    for(int i = 0; i<=h; i++) {
        for(int j = 0; j <= w; j++) {
            if(gr[i][j] == 0) {
                que.push({i, j});
            }
        }   
    }
    while(que.size()) {
        auto cur = que.front();
        que.pop();
        for(int i = 1; i<=4; i++) {
            auto tmp = cur;
            REP(j, 2) tmp[j] += dir[i][j];
            if(0 <= tmp[0] && tmp[0] <= h && 0 <= tmp[1] && tmp[1] <= w) {
                if(gr[tmp[0]][tmp[1]] != -1) continue;
                gr[tmp[0]][tmp[1]] = gr[cur[0]][cur[1]] + 1;
                que.push(tmp);
            }
        }
    }
    for(int i = 0; i<=h; i++) {
        for(int j = 0; j <= w; j++) {
            gr[i][j] *= C;
        }
    }
}

void dijkstra(vector<vector<array<lli,5> > > &sp) {
    sp.assign(h + 3, vector<array<lli,5> >(w + 3, {INF, INF, INF, INF, INF}));
    priority_queue<pair<lli, array<int, 3> >, vector<pair<lli, array<int, 3> > >, greater<pair<lli, array<int, 3> > > > pq;
    pq.push(MP(0ll, array<int,3>({s[0], s[1], 0})));
    while(pq.size()) {
        auto cur = pq.top();
        pq.pop();
        if(sp[cur.second[0]][cur.second[1]][cur.second[2]] != INF) {
            continue;
        } 
        sp[cur.second[0]][cur.second[1]][cur.second[2]] = cur.first;
        if(cur.second[2]) {
            auto tmp = cur.second;
            tmp[2] = 0;
            if(sp[tmp[0]][tmp[1]][tmp[2]] == INF) {         // go ground
                pq.push(MP(cur.first + gr[tmp[0]][tmp[1]], tmp));
            }
            tmp = cur.second;
            REP(j, 2) {
                tmp[j] += dir[tmp[2]][j];
                
            }
            if(0 <= tmp[0] && tmp[0] <= h && 0 <= tmp[1] && tmp[1] <= w && sp[tmp[0]][tmp[1]][tmp[2]] == INF) {
                pq.push(MP(cur.first + A, tmp));
            }
            
        }
        else {
            for(int i = 1; i<=4; i++) {
                auto tmp = cur.second;
                REP(j, 2) {
                    tmp[j] += dir[i][j];  
                }  
                if(0 <= tmp[0] && tmp[0] <= h && 0 <= tmp[1] && tmp[1] <= w && sp[tmp[0]][tmp[1]][tmp[2]] == INF) {
                    pq.push(MP(cur.first + C, tmp));
                }   
            }
            auto tmp = cur.second;
            for(int i = 1; i<=4; i++) {
                tmp[2] = i;
                if(sp[tmp[0]][tmp[1]][tmp[2]] == INF) {
                    pq.push(MP(cur.first + B, tmp));
                }
            }
        }
    } 
}

inline void solve() {
    cin >> h >> w;
    cin >> A >> B >> C;
    cin >> n;
    gr.assign(h + 3, vector<lli>(w + 3, -1));
    for(int i = 1; i<=n; i++) {
        int x, y;
        cin >> x >> y;
        gr[x][y] = 0;
        if(i == 1) {
            s = {x, y};
        }
        if(i == n) {
            t = {x, y};
        }
    }
    bfs();
    vector<vector<array<lli, 5> > > sp;
    dijkstra(sp);
    cout << sp[t[0]][t[1]][0] << "\n";
}
 
signed main() {
    dir[1] = {1, 0}; dir[2] = {-1, 0};
    dir[3] = {0, 1}; dir[4] = {0, -1};
    //fastio();
    int test = 1;
    //cin>>test;
    while(test--) {
        solve();
    }
    
}

• Subtask 1: 5 / 5
• Subtask 2: 30 / 30
• Subtask 3: 65 / 65