oj.uz

Submission #837330

# Submission time Handle Problem Language Result Execution time Memory
837330 2023-08-25T09:36:58 Z _martynas Soccer (JOI17_soccer) C++11
100 / 100
 344 ms 22660 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int mxh = 505;
const int mxn = 1e5+5;
const ll inf = 1e17;

int h, w, n;
ll A, B, C;
ll s[mxn], t[mxn];
ll dist[mxh][mxh][5]; // 4 - with player, 0-3 - directions
int closest[mxh][mxh];
int diri[4] = {0, 1, 0, -1};
int dirj[4] = {1, 0, -1, 0};

struct Info {
    ll d, i, j, k;
    bool operator<(const Info& other) const {
        return d > other.d;
    }
};

bool in(int i, int j) {
    return i >= 0 && i < h && j >= 0 && j < w;
}

void bfs() {
    queue<pair<int, int>> q;
    vector<vector<bool>> visited(h, vector<bool>(w));
    for(int i = 0; i < n; i++) {
        visited[s[i]][t[i]] = true;
        closest[s[i]][t[i]] = 0;
        q.push({s[i], t[i]});
    }
    while(!q.empty()) {
        int i = q.front().first;
        int j = q.front().second;
        q.pop();
        for(int d = 0; d < 4; d++) {
            int ni = i+diri[d], nj = j+dirj[d];
            if(in(ni, nj) && !visited[ni][nj]) {
                closest[ni][nj] = closest[i][j]+1;
                visited[ni][nj] = true;
                q.push({ni, nj});
            }
        }
    }
}

int main(int argc, char const *argv[]) {
    cin >> h >> w >> A >> B >> C; h++, w++;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> s[i] >> t[i];
    if(C <= A) {
        cout << C*(labs(s[0]-s[n-1])+labs(t[0]-t[n-1])) << "\n";
        return 0;
    }
    for(int i = 0; i < h; i++) {
        for(int j = 0; j < w; j++) {
            for(int k = 0; k < 5; k++) dist[i][j][k] = inf;
        }
    }
    bfs();
    priority_queue<Info> pq;
    dist[s[0]][t[0]][4] = 0;
    pq.push(Info{dist[s[0]][t[0]][4], s[0], t[0], 4});
    while(!pq.empty()) {
        Info c = pq.top();
        pq.pop();
        if(dist[c.i][c.j][c.k] != c.d) continue;
        // cout << c.i << " " << c.j << " " << c.k << ": " << c.d << "\n";
        if(c.k == 4) {
            // ball with a player
            // walk again
            for(int d = 0; d < 4; d++) {
                int ni = c.i+diri[d], nj = c.j+dirj[d];
                if(in(ni, nj) && dist[ni][nj][4] > c.d+C) {
                    dist[ni][nj][4] = c.d+C;
                    // printf("push: %lld %d %d %d\n", dist[ni][nj][4], ni, nj, 4);
                    pq.push(Info{dist[ni][nj][4], ni, nj, 4});
                }
            }
            // kick the ball
            for(int d = 0; d < 4; d++) {
                int ni = c.i+diri[d], nj = c.j+dirj[d];
                if(in(ni, nj) && dist[ni][nj][d] > c.d+A+B) {
                    dist[ni][nj][d] = c.d+A+B;
                    // printf("push: %lld %d %d %d\n", dist[ni][nj][d], ni, nj, d);
                    pq.push(Info{dist[ni][nj][d], ni, nj, d});
                }
            }
        }
        else {
            // ball w/o a player
            // continue flying
            int ni = c.i+diri[c.k], nj = c.j+dirj[c.k];
            if(in(ni, nj) && dist[ni][nj][c.k] > c.d+A) {
                dist[ni][nj][c.k] = c.d+A;
                // printf("push: %lld %d %d %d\n", dist[ni][nj][c.k], ni, nj, c.k);
                pq.push(Info{dist[ni][nj][c.k], ni, nj, c.k});
            }
            // find closest player to kick
            if(dist[c.i][c.j][4] > c.d+C*closest[c.i][c.j]) {
                dist[c.i][c.j][4] = c.d+C*closest[c.i][c.j];
                pq.push(Info{dist[c.i][c.j][4], c.i, c.j, 4});
            }
        }
    }
    ll ans = inf;
    for(int k = 0; k < 5; k++) ans = min(ans, dist[s[n-1]][t[n-1]][k]);
    cout << ans << "\n";
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 6596 KB Output is correct
2 Correct 0 ms 296 KB Output is correct
3 Correct 225 ms 19564 KB Output is correct
4 Correct 239 ms 19492 KB Output is correct
5 Correct 1 ms 212 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 19488 KB Output is correct
2 Correct 273 ms 19520 KB Output is correct
3 Correct 182 ms 17580 KB Output is correct
4 Correct 175 ms 19560 KB Output is correct
5 Correct 218 ms 19544 KB Output is correct
6 Correct 204 ms 19536 KB Output is correct
7 Correct 240 ms 19628 KB Output is correct
8 Correct 228 ms 19548 KB Output is correct
9 Correct 237 ms 19612 KB Output is correct
10 Correct 30 ms 7112 KB Output is correct
11 Correct 218 ms 19620 KB Output is correct
12 Correct 251 ms 19612 KB Output is correct
13 Correct 147 ms 17348 KB Output is correct
14 Correct 219 ms 19588 KB Output is correct
15 Correct 178 ms 19556 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 6596 KB Output is correct
2 Correct 0 ms 296 KB Output is correct
3 Correct 225 ms 19564 KB Output is correct
4 Correct 239 ms 19492 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 251 ms 19488 KB Output is correct
7 Correct 273 ms 19520 KB Output is correct
8 Correct 182 ms 17580 KB Output is correct
9 Correct 175 ms 19560 KB Output is correct
10 Correct 218 ms 19544 KB Output is correct
11 Correct 204 ms 19536 KB Output is correct
12 Correct 240 ms 19628 KB Output is correct
13 Correct 228 ms 19548 KB Output is correct
14 Correct 237 ms 19612 KB Output is correct
15 Correct 30 ms 7112 KB Output is correct
16 Correct 218 ms 19620 KB Output is correct
17 Correct 251 ms 19612 KB Output is correct
18 Correct 147 ms 17348 KB Output is correct
19 Correct 219 ms 19588 KB Output is correct
20 Correct 178 ms 19556 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 289 ms 19536 KB Output is correct
23 Correct 265 ms 14472 KB Output is correct
24 Correct 324 ms 15556 KB Output is correct
25 Correct 274 ms 19636 KB Output is correct
26 Correct 281 ms 19696 KB Output is correct
27 Correct 20 ms 1916 KB Output is correct
28 Correct 147 ms 14676 KB Output is correct
29 Correct 265 ms 18148 KB Output is correct
30 Correct 131 ms 14428 KB Output is correct
31 Correct 244 ms 19668 KB Output is correct
32 Correct 344 ms 22660 KB Output is correct
33 Correct 210 ms 19600 KB Output is correct
34 Correct 319 ms 19700 KB Output is correct
35 Correct 28 ms 2588 KB Output is correct