oj.uz

Submission #337219

# Submission time Handle Problem Language Result Execution time Memory
337219 2020-12-19T00:31:45 Z thecodingwizard Soccer (JOI17_soccer) C++11
100 / 100
 590 ms 19936 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define ii pair<int, int>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define F0R(i, n) for (int i = 0; i < n; i++)
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define inf 1000000010

int h, w; 
// min dist to get a player to (i, j)
ll getPlayer[501][501];
// min cost to get ball to (i, j)
// {0-3}: direction the ball is currently traveling (kicked)
// 4: The ball has landed and a person is currently holding it
ll dist[501][501][5];
ll a, b, c;

bool g(ii x) {
    return x.f >= 0 && x.f <= h && x.s >= 0 && x.s <= w;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);

    cin >> h >> w;
    F0R(i, h+1) F0R(j, w+1) getPlayer[i][j] = 1e18;
    F0R(i, h+1) F0R(j, w+1) F0R(k, 5) dist[i][j][k] = 1e18;
    cin >> a >> b >> c;
    int n; cin >> n;
    queue<ii> q;
    ii first;
    F0R(i, n-1) {
        int x, y; cin >> x >> y; q.push(mp(x, y));
        if (i == 0) first = mp(x,y);
        getPlayer[x][y] = 0;
    }
    int dx[4]{-1,0,1,0};
    int dy[4]{0,-1,0,1};
    while (!q.empty()) {
        ii u = q.front(); q.pop();
        F0R(i, 4) {
            ii v = mp(u.f+dx[i], u.s+dy[i]);
            if (g(v) && getPlayer[v.f][v.s] == 1e18) {
                getPlayer[v.f][v.s] = getPlayer[u.f][u.s]+1;
                q.push(v);
            }
        }
    }
    ii dest; cin >> dest.f >> dest.s;

    priority_queue<pair<ll, pair<ii, int>>, vector<pair<ll, pair<ii, int>>>, greater<pair<ll, pair<ii, int>>>> pq;
    pq.push(mp(0, mp(first, 4)));
    dist[first.f][first.s][4] = 0;
    while (!pq.empty()) {
        pair<ll, pair<ii, int>> top = pq.top(); pq.pop();
        ll d = top.f;
        ii u = top.s.f;
        int dir = top.s.s;
        if (dist[u.f][u.s][dir] != d) continue;
        
        if (dir == 4) {
            // choose a direction and kick it
            F0R(i, 4) {
                ii v = u;
                if (g(v) && dist[v.f][v.s][i] > d+b) {
                    dist[v.f][v.s][i] = d+b;
                    pq.push(mp(d+b, mp(v, i)));
                }
            }
            // or, choose a direction and move
            F0R(i, 4) {
                ii v = mp(u.f+dx[i], u.s+dy[i]);
                if (g(v) && dist[v.f][v.s][4] > d+c) {
                    dist[v.f][v.s][4] = d+c;
                    pq.push(mp(d+c, mp(v, 4)));
                }
            }
        } else {
            // keep kicking it
            ii v = mp(u.f+dx[dir], u.s+dy[dir]);
            if (g(v) && dist[v.f][v.s][dir] > d+a) {
                dist[v.f][v.s][dir] = d+a;
                pq.push(mp(d+a, mp(v, dir)));
            }
            // stop, get somebody to pick it up
            if (dist[u.f][u.s][4] > d+getPlayer[u.f][u.s]*c) {
                dist[u.f][u.s][4] = d+getPlayer[u.f][u.s]*c;
                pq.push(mp(d+getPlayer[u.f][u.s]*c, mp(u, 4)));
            }
        }
    }

    ll ans = dist[dest.f][dest.s][4];
    F0R(i, 4) ans = min(ans, dist[dest.f][dest.s][i]);
    cout << ans << endl;

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 6756 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 362 ms 18400 KB Output is correct
4 Correct 359 ms 18400 KB Output is correct
5 Correct 88 ms 6892 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 458 ms 18404 KB Output is correct
2 Correct 468 ms 18408 KB Output is correct
3 Correct 325 ms 16260 KB Output is correct
4 Correct 313 ms 18420 KB Output is correct
5 Correct 338 ms 18420 KB Output is correct
6 Correct 342 ms 18524 KB Output is correct
7 Correct 448 ms 18572 KB Output is correct
8 Correct 387 ms 18548 KB Output is correct
9 Correct 453 ms 18700 KB Output is correct
10 Correct 68 ms 7676 KB Output is correct
11 Correct 436 ms 18572 KB Output is correct
12 Correct 458 ms 18420 KB Output is correct
13 Correct 246 ms 16096 KB Output is correct
14 Correct 453 ms 18572 KB Output is correct
15 Correct 346 ms 18572 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 6756 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 362 ms 18400 KB Output is correct
4 Correct 359 ms 18400 KB Output is correct
5 Correct 88 ms 6892 KB Output is correct
6 Correct 458 ms 18404 KB Output is correct
7 Correct 468 ms 18408 KB Output is correct
8 Correct 325 ms 16260 KB Output is correct
9 Correct 313 ms 18420 KB Output is correct
10 Correct 338 ms 18420 KB Output is correct
11 Correct 342 ms 18524 KB Output is correct
12 Correct 448 ms 18572 KB Output is correct
13 Correct 387 ms 18548 KB Output is correct
14 Correct 453 ms 18700 KB Output is correct
15 Correct 68 ms 7676 KB Output is correct
16 Correct 436 ms 18572 KB Output is correct
17 Correct 458 ms 18420 KB Output is correct
18 Correct 246 ms 16096 KB Output is correct
19 Correct 453 ms 18572 KB Output is correct
20 Correct 346 ms 18572 KB Output is correct
21 Correct 93 ms 6832 KB Output is correct
22 Correct 566 ms 18596 KB Output is correct
23 Correct 524 ms 14452 KB Output is correct
24 Correct 590 ms 15520 KB Output is correct
25 Correct 452 ms 18536 KB Output is correct
26 Correct 490 ms 18716 KB Output is correct
27 Correct 303 ms 13676 KB Output is correct
28 Correct 297 ms 14060 KB Output is correct
29 Correct 435 ms 17008 KB Output is correct
30 Correct 255 ms 13932 KB Output is correct
31 Correct 467 ms 18700 KB Output is correct
32 Correct 562 ms 19936 KB Output is correct
33 Correct 354 ms 18400 KB Output is correct
34 Correct 578 ms 18572 KB Output is correct
35 Correct 251 ms 13804 KB Output is correct