oj.uz

Submission #397289

# Submission time Handle Problem Language Result Execution time Memory
397289 2021-05-01T20:24:56 Z timmyfeng Soccer (JOI17_soccer) C++17
100 / 100
 547 ms 22052 KB 
#include <bits/stdc++.h>
using namespace std;

const int X[] = {1, 0, -1, 0}, Y[] = {0, 1, 0, -1};
const int N = 501, M = 100001;

priority_queue<array<long long, 4>> dijkstra;
long long player[N][N], dist[N][N][5];
array<int, 2> coord[M];
int h, w;

void update(int x, int y, int z, long long d) {
    if (0 <= x && x <= h && 0 <= y && y <= w && d < dist[x][y][z]) {
        dist[x][y][z] = d;
        dijkstra.push({-d, x, y, z});
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    long long a, b, c;
    cin >> h >> w >> a >> b >> c >> n;

    for (int i = 0; i <= h; ++i) {
        for (int j = 0; j <= w; ++j) {
            player[i][j] = -1;
            for (int k = 0; k < 5; ++k) {
                dist[i][j][k] = LLONG_MAX;
            }
        }
    }

    for (int i = 0; i < n; ++i) {
        auto &[x, y] = coord[i];
        cin >> x >> y;
    }

    queue<array<int, 2>> bfs;
    for (int i = 0; i < n - 1; ++i) {
        auto [x, y] = coord[i];
        if (player[x][y] == -1) {
            player[x][y] = 0;
            bfs.push({x, y});
        }
    }

    while (!bfs.empty()) {
        auto [x, y] = bfs.front();
        bfs.pop();
        for (int i = 0; i < 4; ++i) {
            int xn = x + X[i];
            int yn = y + Y[i];
            if (0 <= xn && xn <= h && 0 <= yn && yn <= w && player[xn][yn] == -1) {
                player[xn][yn] = player[x][y] + c;
                bfs.push({xn, yn});
            }
        }
    }
    player[coord[n - 1][0]][coord[n - 1][1]] = 0;

    dijkstra.push({0, coord[0][0], coord[0][1], 4});
    dist[coord[0][0]][coord[0][1]][4] = 0;

    while (!dijkstra.empty()) {
        auto [d, x, y, z] = dijkstra.top();
        dijkstra.pop();
        d = -d;

        if (d > dist[x][y][z]) {
            continue;
        }

        if (z == 4) {
            for (int i = 0; i < 4; ++i) {
                update(x, y, i, d + b);
                int xn = x + X[i];
                int yn = y + Y[i];
                update(xn, yn, 4, d + c);
            }
        } else {
            int xn = x + X[z];
            int yn = y + Y[z];
            update(xn, yn, z, d + a);
            update(x, y, 4, d + player[x][y]);
        }
    }

    cout << dist[coord[n - 1][0]][coord[n - 1][1]][4] << "\n";
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 7236 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 369 ms 20396 KB Output is correct
4 Correct 369 ms 20400 KB Output is correct
5 Correct 93 ms 6772 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 423 ms 20432 KB Output is correct
2 Correct 431 ms 20408 KB Output is correct
3 Correct 310 ms 18096 KB Output is correct
4 Correct 304 ms 20364 KB Output is correct
5 Correct 322 ms 20416 KB Output is correct
6 Correct 321 ms 20436 KB Output is correct
7 Correct 437 ms 20512 KB Output is correct
8 Correct 385 ms 20468 KB Output is correct
9 Correct 447 ms 20464 KB Output is correct
10 Correct 66 ms 8164 KB Output is correct
11 Correct 427 ms 20580 KB Output is correct
12 Correct 422 ms 20412 KB Output is correct
13 Correct 248 ms 18100 KB Output is correct
14 Correct 422 ms 20468 KB Output is correct
15 Correct 333 ms 20396 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 7236 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 369 ms 20396 KB Output is correct
4 Correct 369 ms 20400 KB Output is correct
5 Correct 93 ms 6772 KB Output is correct
6 Correct 423 ms 20432 KB Output is correct
7 Correct 431 ms 20408 KB Output is correct
8 Correct 310 ms 18096 KB Output is correct
9 Correct 304 ms 20364 KB Output is correct
10 Correct 322 ms 20416 KB Output is correct
11 Correct 321 ms 20436 KB Output is correct
12 Correct 437 ms 20512 KB Output is correct
13 Correct 385 ms 20468 KB Output is correct
14 Correct 447 ms 20464 KB Output is correct
15 Correct 66 ms 8164 KB Output is correct
16 Correct 427 ms 20580 KB Output is correct
17 Correct 422 ms 20412 KB Output is correct
18 Correct 248 ms 18100 KB Output is correct
19 Correct 422 ms 20468 KB Output is correct
20 Correct 333 ms 20396 KB Output is correct
21 Correct 101 ms 6868 KB Output is correct
22 Correct 494 ms 20460 KB Output is correct
23 Correct 457 ms 15152 KB Output is correct
24 Correct 547 ms 16444 KB Output is correct
25 Correct 432 ms 20400 KB Output is correct
26 Correct 470 ms 20684 KB Output is correct
27 Correct 309 ms 14276 KB Output is correct
28 Correct 289 ms 14740 KB Output is correct
29 Correct 419 ms 18196 KB Output is correct
30 Correct 253 ms 14284 KB Output is correct
31 Correct 419 ms 20484 KB Output is correct
32 Correct 528 ms 22052 KB Output is correct
33 Correct 339 ms 20400 KB Output is correct
34 Correct 542 ms 20516 KB Output is correct
35 Correct 246 ms 13924 KB Output is correct