oj.uz

Submission #520017

# Submission time Handle Problem Language Result Execution time Memory
520017 2022-01-28T06:29:59 Z Giantpizzahead Soccer (JOI17_soccer) C++17
100 / 100
 403 ms 18672 KB 
/*
Must solve using some form of modified Dijkstra
If A >= C, never makes sense to kick the ball, special case
Now guaranteed A < C

When a player has the ball, they can either kick to any square in their row / column (Ap + B), or move to a different square (C)

It may be optimal to move before getting the ball, but it's never optimal to have the same player get the ball twice (they could just move with the ball instead).

BFS to find shortest distance from each cell to the nearest player. If the ball is at that cell, players can get to the ball with that distance.

When kicking the ball, don't transition to all cells immediately; treat it as another state to reach.

So each cell location has states of: Player has the ball (4), no one has the ball (5), ball is currently being kicked in any of 4 directions (0-1-2-3).

Trans: 5 -> 4, 4 -> 0-1-2-3, 0-1-2-3 -> 5

This works because even though it doesn't correctly consider the "move back" cost for a player, it's never optimal for the same player to get the ball twice, and any state that uses the same player twice will be greater cost than the correct, optimal path. (Although some paths will have incorrect cost, they won't be the ones the algorithm chooses.)

Runtime: O(HW * log(HW))
*/

#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define sz(x) ((int) x.size())
#define all(x) x.begin(), x.end()
#define debug if (true) cerr
using ll = long long;

const int MAXD = 505;
const ll INF = 1e18;

int H, W, N;
int si, sj, ei, ej;
ll A, B, C;
ll costP[MAXD][MAXD];

int ci[] = {1, 0, -1, 0}, cj[] = {0, 1, 0, -1};

inline bool inBounds(int i, int j) {
    return i >= 0 && i < H && j >= 0 && j < W;
}

// 0-3 = Being kicked, 4 = Player has the ball
ll bestC[MAXD][MAXD][5];
struct Loc {
    int i, j, k;
    ll c;
    bool operator<(const Loc& o) const {
        return c > o.c;
    }
};
priority_queue<Loc> pq;

void tryTrans(int i, int j, int k, ll c) {
    if (!inBounds(i, j) || bestC[i][j][k] <= c) return;
    bestC[i][j][k] = c;
    pq.push({i, j, k, c});
}

void bfs1() {
    while (!pq.empty()) {
        Loc l = pq.top(); pq.pop();
        int i = l.i, j = l.j;
        ll c = l.c;
        if (c != costP[i][j]) continue;
        // Move to adjacent square
        rep(d, 0, 4) {
            int ni = i + ci[d], nj = j + cj[d];
            ll nc = c + C;
            if (!inBounds(ni, nj) || costP[ni][nj] <= nc) continue;
            costP[ni][nj] = nc;
            pq.push({ni, nj, -1, nc});
        }
    }
}

void bfs2() {
    bestC[si][sj][4] = 0;
    pq.push({si, sj, 4, 0});
    while (!pq.empty()) {
        Loc l = pq.top(); pq.pop();
        int i = l.i, j = l.j, k = l.k;
        ll c = l.c;
        if (c != bestC[i][j][k]) continue;
        if (k == 4) {
            // Player has the ball
            rep(d, 0, 4) {
                tryTrans(i + ci[d], j + cj[d], 4, c + C);  // Move with the ball
                tryTrans(i, j, d, c + B);  // Kick the ball in a direction
            }
        } else {
            // Ball is being kicked
            // Continue moving the ball
            tryTrans(i + ci[k], j + cj[k], k, c + A);
            // Stop moving and have a player pick up the ball
            tryTrans(i, j, 4, c + costP[i][j]);
        }
    }
}

void solve() {
    cin >> H >> W;
    H++, W++;
    cin >> A >> B >> C;
    cin >> N;
    rep(i, 0, H) rep(j, 0, W) {
        costP[i][j] = INF;
        rep(k, 0, 5) bestC[i][j][k] = INF;
    }
    rep(k, 0, N) {
        int i, j; cin >> i >> j;
        if (k == 0) si = i, sj = j;
        else if (k == N-1) ei = i, ej = j;
        costP[i][j] = 0;
        pq.push({i, j, -1, 0});
    }
    bfs1();
    bfs2();
    ll ans = INF;
    rep(i, 0, H) rep(j, 0, W) rep(k, 0, 5) {
        ll cost = bestC[i][j][k] + C * (abs(ei-i) + abs(ej-j));
        ans = min(cost, ans);
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 6724 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 275 ms 18476 KB Output is correct
4 Correct 301 ms 18384 KB Output is correct
5 Correct 48 ms 6788 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 18388 KB Output is correct
2 Correct 321 ms 18408 KB Output is correct
3 Correct 222 ms 16044 KB Output is correct
4 Correct 226 ms 18416 KB Output is correct
5 Correct 240 ms 18388 KB Output is correct
6 Correct 244 ms 18408 KB Output is correct
7 Correct 316 ms 18476 KB Output is correct
8 Correct 292 ms 18440 KB Output is correct
9 Correct 323 ms 18480 KB Output is correct
10 Correct 41 ms 7492 KB Output is correct
11 Correct 329 ms 18436 KB Output is correct
12 Correct 365 ms 18472 KB Output is correct
13 Correct 192 ms 16040 KB Output is correct
14 Correct 320 ms 18396 KB Output is correct
15 Correct 239 ms 18428 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 6724 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 275 ms 18476 KB Output is correct
4 Correct 301 ms 18384 KB Output is correct
5 Correct 48 ms 6788 KB Output is correct
6 Correct 307 ms 18388 KB Output is correct
7 Correct 321 ms 18408 KB Output is correct
8 Correct 222 ms 16044 KB Output is correct
9 Correct 226 ms 18416 KB Output is correct
10 Correct 240 ms 18388 KB Output is correct
11 Correct 244 ms 18408 KB Output is correct
12 Correct 316 ms 18476 KB Output is correct
13 Correct 292 ms 18440 KB Output is correct
14 Correct 323 ms 18480 KB Output is correct
15 Correct 41 ms 7492 KB Output is correct
16 Correct 329 ms 18436 KB Output is correct
17 Correct 365 ms 18472 KB Output is correct
18 Correct 192 ms 16040 KB Output is correct
19 Correct 320 ms 18396 KB Output is correct
20 Correct 239 ms 18428 KB Output is correct
21 Correct 57 ms 6708 KB Output is correct
22 Correct 363 ms 18672 KB Output is correct
23 Correct 323 ms 14132 KB Output is correct
24 Correct 377 ms 15360 KB Output is correct
25 Correct 327 ms 18380 KB Output is correct
26 Correct 326 ms 18452 KB Output is correct
27 Correct 200 ms 15424 KB Output is correct
28 Correct 177 ms 18492 KB Output is correct
29 Correct 296 ms 15424 KB Output is correct
30 Correct 167 ms 15424 KB Output is correct
31 Correct 336 ms 18460 KB Output is correct
32 Correct 403 ms 18476 KB Output is correct
33 Correct 270 ms 18484 KB Output is correct
34 Correct 390 ms 18396 KB Output is correct
35 Correct 162 ms 15424 KB Output is correct