oj.uz

Submission #234004

# Submission time Handle Problem Language Result Execution time Memory
234004 2020-05-22T18:25:11 Z dolphingarlic Soccer (JOI17_soccer) C++14
0 / 100
 3000 ms 211360 KB 
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef unsigned long long ll;
using namespace std;

struct Ball {
    int x, y, d;
    ll f;
};

bool operator<(Ball A, Ball B) { return A.f > B.f; }

int h, w;
ll vert[501][501], to_p[501][501], visited[501][501][5];
int dx[5]{0, 0, 0, 1, -1}, dy[5]{0, 1, -1, 0, 0};

bool inside(int x, int y) {
    return (~x && ~y && x <= h && y <= w);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    ll a, b, c;
    Ball dest;
    priority_queue<Ball> pq;
    cin >> h >> w >> a >> b >> c >> n;

    memset(vert, 0x3f, sizeof(vert));
    memset(to_p, 0x3f, sizeof(to_p));
    FOR(i, 0, n) {
        int x, y;
        cin >> x >> y;
        vert[x][y] = 0;
        if (!i) pq.push({x, y, 0, 1});
        if (i == n - 1) dest = {x, y, 0, 1};
    }

    FOR(i, 0, h + 1) FOR(j, 0, w + 1) {
        if (i) vert[i][j] = min(vert[i][j], vert[i - 1][j] + 1);
        if (i < h) vert[n - i][j] = min(vert[n - i][j], vert[n - i + 1][j] + 1);
    }
    FOR(i, 0, h + 1) FOR(j, 0, w + 1) FOR(k, 0, w + 1)
        to_p[i][j] = min(to_p[i][j], vert[i][k] + abs(j - k));
    
    while (pq.size()) {
        Ball curr = pq.top();
        pq.pop();
        if (visited[curr.x][curr.y][curr.d]) continue;

        visited[curr.x][curr.y][curr.d] = curr.f;
        if (curr.d) { // Ball is at (x, y) and is/was moving in direction d
            // Ball continues in the direction
            if (inside(curr.x + dx[curr.d], curr.y + dy[curr.d]))
                pq.push({curr.x + dx[curr.d], curr.y + dy[curr.d], curr.d, curr.f + a});
            // Ball stops and player runs to it
            curr.f += to_p[curr.x][curr.y] * c;
        }
        // Player has ball at (x, y)
        FOR(i, 1, 5) {
            int nx = curr.x + dx[i], ny = curr.y + dy[i];
            if (inside(nx, ny)) {
                // Player runs in direction i with the ball
                pq.push({nx, ny, 0, curr.f + c});
                // Player kicks the ball in direction i
                pq.push({nx, ny, i, curr.f + a + b});
            }
        }
    }

    ll ans = LLONG_MAX;
    FOR(i, 0, 5) ans = min(ans, visited[dest.x][dest.y][i] - 1);
    cout << ans;
    return 0;
}

Compilation message

soccer.cpp: In function 'int main()':
soccer.cpp:26:10: warning: 'dest.Ball::y' may be used uninitialized in this function [-Wmaybe-uninitialized]
     Ball dest;
          ^~~~
soccer.cpp:26:10: warning: 'dest.Ball::x' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 719 ms 57260 KB Output is correct
2 Correct 7 ms 4480 KB Output is correct
3 Execution timed out 3089 ms 211220 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3104 ms 211360 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 719 ms 57260 KB Output is correct
2 Correct 7 ms 4480 KB Output is correct
3 Execution timed out 3089 ms 211220 KB Time limit exceeded
4 Halted 0 ms 0 KB -