oj.uz

Submission #965532

# Submission time Handle Problem Language Result Execution time Memory
965532 2024-04-18T19:40:03 Z efedmrlr Soccer (JOI17_soccer) C++17
100 / 100
 686 ms 39100 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 96 ms 6356 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 378 ms 20568 KB Output is correct
4 Correct 423 ms 25024 KB Output is correct
5 Correct 110 ms 4956 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 601 ms 38848 KB Output is correct
2 Correct 565 ms 37852 KB Output is correct
3 Correct 380 ms 23440 KB Output is correct
4 Correct 444 ms 20184 KB Output is correct
5 Correct 399 ms 24264 KB Output is correct
6 Correct 414 ms 24784 KB Output is correct
7 Correct 611 ms 38680 KB Output is correct
8 Correct 473 ms 39100 KB Output is correct
9 Correct 625 ms 37320 KB Output is correct
10 Correct 81 ms 5584 KB Output is correct
11 Correct 597 ms 37272 KB Output is correct
12 Correct 582 ms 38360 KB Output is correct
13 Correct 328 ms 24012 KB Output is correct
14 Correct 611 ms 38104 KB Output is correct
15 Correct 508 ms 35704 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 6356 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 378 ms 20568 KB Output is correct
4 Correct 423 ms 25024 KB Output is correct
5 Correct 110 ms 4956 KB Output is correct
6 Correct 601 ms 38848 KB Output is correct
7 Correct 565 ms 37852 KB Output is correct
8 Correct 380 ms 23440 KB Output is correct
9 Correct 444 ms 20184 KB Output is correct
10 Correct 399 ms 24264 KB Output is correct
11 Correct 414 ms 24784 KB Output is correct
12 Correct 611 ms 38680 KB Output is correct
13 Correct 473 ms 39100 KB Output is correct
14 Correct 625 ms 37320 KB Output is correct
15 Correct 81 ms 5584 KB Output is correct
16 Correct 597 ms 37272 KB Output is correct
17 Correct 582 ms 38360 KB Output is correct
18 Correct 328 ms 24012 KB Output is correct
19 Correct 611 ms 38104 KB Output is correct
20 Correct 508 ms 35704 KB Output is correct
21 Correct 113 ms 5468 KB Output is correct
22 Correct 541 ms 26208 KB Output is correct
23 Correct 553 ms 24752 KB Output is correct
24 Correct 596 ms 25316 KB Output is correct
25 Correct 428 ms 25980 KB Output is correct
26 Correct 494 ms 18784 KB Output is correct
27 Correct 287 ms 13144 KB Output is correct
28 Correct 361 ms 13348 KB Output is correct
29 Correct 441 ms 16736 KB Output is correct
30 Correct 383 ms 14808 KB Output is correct
31 Correct 596 ms 37520 KB Output is correct
32 Correct 686 ms 38624 KB Output is correct
33 Correct 378 ms 25552 KB Output is correct
34 Correct 682 ms 38340 KB Output is correct
35 Correct 311 ms 13380 KB Output is correct