oj.uz

Submission #965533

# Submission time Handle Problem Language Result Execution time Memory
965533 2024-04-18T19:40:15 Z efedmrlr Soccer (JOI17_soccer) C++17
100 / 100
 674 ms 38840 KB 
// #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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 6360 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 409 ms 18928 KB Output is correct
4 Correct 431 ms 25612 KB Output is correct
5 Correct 109 ms 4956 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 635 ms 38596 KB Output is correct
2 Correct 606 ms 37388 KB Output is correct
3 Correct 378 ms 23592 KB Output is correct
4 Correct 450 ms 18648 KB Output is correct
5 Correct 407 ms 23908 KB Output is correct
6 Correct 426 ms 26060 KB Output is correct
7 Correct 674 ms 38164 KB Output is correct
8 Correct 478 ms 37720 KB Output is correct
9 Correct 638 ms 37060 KB Output is correct
10 Correct 78 ms 6864 KB Output is correct
11 Correct 608 ms 38840 KB Output is correct
12 Correct 588 ms 38108 KB Output is correct
13 Correct 332 ms 24012 KB Output is correct
14 Correct 598 ms 38604 KB Output is correct
15 Correct 461 ms 36180 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 6360 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 409 ms 18928 KB Output is correct
4 Correct 431 ms 25612 KB Output is correct
5 Correct 109 ms 4956 KB Output is correct
6 Correct 635 ms 38596 KB Output is correct
7 Correct 606 ms 37388 KB Output is correct
8 Correct 378 ms 23592 KB Output is correct
9 Correct 450 ms 18648 KB Output is correct
10 Correct 407 ms 23908 KB Output is correct
11 Correct 426 ms 26060 KB Output is correct
12 Correct 674 ms 38164 KB Output is correct
13 Correct 478 ms 37720 KB Output is correct
14 Correct 638 ms 37060 KB Output is correct
15 Correct 78 ms 6864 KB Output is correct
16 Correct 608 ms 38840 KB Output is correct
17 Correct 588 ms 38108 KB Output is correct
18 Correct 332 ms 24012 KB Output is correct
19 Correct 598 ms 38604 KB Output is correct
20 Correct 461 ms 36180 KB Output is correct
21 Correct 114 ms 5468 KB Output is correct
22 Correct 528 ms 26912 KB Output is correct
23 Correct 538 ms 24768 KB Output is correct
24 Correct 571 ms 25164 KB Output is correct
25 Correct 404 ms 26568 KB Output is correct
26 Correct 471 ms 19928 KB Output is correct
27 Correct 273 ms 12564 KB Output is correct
28 Correct 340 ms 12664 KB Output is correct
29 Correct 426 ms 16848 KB Output is correct
30 Correct 350 ms 14028 KB Output is correct
31 Correct 546 ms 38032 KB Output is correct
32 Correct 631 ms 37280 KB Output is correct
33 Correct 364 ms 25036 KB Output is correct
34 Correct 621 ms 38240 KB Output is correct
35 Correct 291 ms 12912 KB Output is correct