oj.uz

Submission #1066277

# Submission time Handle Problem Language Result Execution time Memory
1066277 2024-08-19T17:18:29 Z sammyuri Soccer (JOI17_soccer) C++17
35 / 100
 3000 ms 138640 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
ll dist[505][505];
ll dist_2[505][505];
ll a, b, c;

ll calc_cost(ll dx, ll dy) {
    ll best = (dx + dy) * c;
    best = min(best, dx * c + b + dy * a);
    best = min(best, dy * c + b + dx * a);
    return best;
}
inline ll pack(pair<ll, pair<int, int>> xx) {
    return xx.first * 360000ll + (600ll * xx.second.first + xx.second.second);
}
inline pair<ll, pair<int, int>> unpack(ll xx) {
    ll k = xx % 360000ll;
    return {xx / 360000ll, {k / 600ll, k % 600ll}};
}
priority_queue<ll> pq;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    memset(dist, -1, sizeof(dist));
    int h, w; cin >> h >> w;
    h ++; w ++;
    cin >> a >> b >> c;
    vector<pair<int, int>> players;
    int n; cin >> n;
    int starti, startj, endi, endj;
    for (int i = 0; i < n; i ++) {
        int s, t; cin >> s >> t;
        players.push_back({s, t});
        if (i == 0)
            starti = s, startj = t;
        else if (i == n - 1)
            endi = s, endj = t;
    }
    // multisource bfs
    queue<pair<int, int>> q;
    for (auto a : players) {
        dist[a.first][a.second] = 0;
        q.push(a);
    }
    while (q.size()) {
        pair<int, int> cur = q.front(); q.pop();
        int curdist = dist[cur.first][cur.second];
        if (cur.first > 0 && dist[cur.first - 1][cur.second] == -1) {
            q.push({cur.first - 1, cur.second});
            dist[cur.first - 1][cur.second] = curdist + 1;
        }
        if (cur.first < h - 1 && dist[cur.first + 1][cur.second] == -1) {
            q.push({cur.first + 1, cur.second});
            dist[cur.first + 1][cur.second] = curdist + 1;
        }
        if (cur.second > 0 && dist[cur.first][cur.second - 1] == -1) {
            q.push({cur.first, cur.second - 1});
            dist[cur.first][cur.second - 1] = curdist + 1;
        }
        if (cur.second < w - 1 && dist[cur.first][cur.second + 1] == -1) {
            q.push({cur.first, cur.second + 1});
            dist[cur.first][cur.second + 1] = curdist + 1;
        }
    }
    // calculate answer
    for (int i = 0; i < h; i ++)
        for (int j = 0; j < w; j ++) {
            // initial distance
            ll curdist = calc_cost(abs(i - starti), abs(j - startj));
            curdist += dist[i][j] * c;
            curdist = min(curdist, abs(i - starti) * c + abs(j - startj) * c);
            dist_2[i][j] = curdist;
            pq.push(-pack({curdist, {i, j}}));
        }
    ll best = 1e18;
    while (pq.size()) {
        auto cur = unpack(-pq.top()); pq.pop();
        ll curdist = cur.first;
        int i = cur.second.first, j = cur.second.second;
        if (dist_2[i][j] != curdist)
            continue;
        // send straight to finish
        // cout << curdist << " " << i << " " << j << endl;
        best = min(best, curdist + calc_cost(abs(i - endi), abs(j - endj)));
        for (int ii = 0; ii < h; ii ++) {
            ll newdist = curdist + calc_cost(abs(ii - i), 0) + dist[ii][j] * c;
            newdist = min(newdist, curdist + abs(ii - i) * c);
            if (dist_2[ii][j] > newdist) {
                dist_2[ii][j] = newdist;
                pq.push(-pack({newdist, {ii, j}}));
            }
        }
        for (int jj = 0; jj < w; jj ++) {
            ll newdist = curdist + calc_cost(abs(jj - j), 0) + dist[i][jj] * c;
            newdist = min(newdist, curdist + abs(jj - j) * c);
            if (dist_2[i][jj] > newdist) {
                dist_2[i][jj] = newdist;
                pq.push(-pack({newdist, {i, jj}}));
            }
        }
    }
    cout << best << endl;
    return 0;
}

Compilation message

soccer.cpp: In function 'int main()':
soccer.cpp:89:67: warning: 'endj' may be used uninitialized in this function [-Wmaybe-uninitialized]
   89 |         best = min(best, curdist + calc_cost(abs(i - endi), abs(j - endj)));
      |                                                                 ~~^~~~~~
soccer.cpp:89:52: warning: 'endi' may be used uninitialized in this function [-Wmaybe-uninitialized]
   89 |         best = min(best, curdist + calc_cost(abs(i - endi), abs(j - endj)));
      |                                                  ~~^~~~~~
soccer.cpp:35:17: warning: 'startj' may be used uninitialized in this function [-Wmaybe-uninitialized]
   35 |     int starti, startj, endi, endj;
      |                 ^~~~~~
soccer.cpp:35:9: warning: 'starti' may be used uninitialized in this function [-Wmaybe-uninitialized]
   35 |     int starti, startj, endi, endj;
      |         ^~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 6604 KB Output is correct
2 Correct 2 ms 4188 KB Output is correct
3 Correct 770 ms 10632 KB Output is correct
4 Correct 1256 ms 37288 KB Output is correct
5 Correct 202 ms 5596 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 828 ms 12948 KB Output is correct
2 Correct 820 ms 13776 KB Output is correct
3 Correct 595 ms 9936 KB Output is correct
4 Correct 750 ms 9168 KB Output is correct
5 Correct 621 ms 8904 KB Output is correct
6 Correct 793 ms 8660 KB Output is correct
7 Correct 816 ms 13060 KB Output is correct
8 Correct 837 ms 12868 KB Output is correct
9 Correct 817 ms 13516 KB Output is correct
10 Correct 106 ms 5584 KB Output is correct
11 Correct 841 ms 13728 KB Output is correct
12 Correct 879 ms 14860 KB Output is correct
13 Correct 541 ms 9940 KB Output is correct
14 Correct 872 ms 14280 KB Output is correct
15 Correct 598 ms 9928 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 6604 KB Output is correct
2 Correct 2 ms 4188 KB Output is correct
3 Correct 770 ms 10632 KB Output is correct
4 Correct 1256 ms 37288 KB Output is correct
5 Correct 202 ms 5596 KB Output is correct
6 Correct 828 ms 12948 KB Output is correct
7 Correct 820 ms 13776 KB Output is correct
8 Correct 595 ms 9936 KB Output is correct
9 Correct 750 ms 9168 KB Output is correct
10 Correct 621 ms 8904 KB Output is correct
11 Correct 793 ms 8660 KB Output is correct
12 Correct 816 ms 13060 KB Output is correct
13 Correct 837 ms 12868 KB Output is correct
14 Correct 817 ms 13516 KB Output is correct
15 Correct 106 ms 5584 KB Output is correct
16 Correct 841 ms 13728 KB Output is correct
17 Correct 879 ms 14860 KB Output is correct
18 Correct 541 ms 9940 KB Output is correct
19 Correct 872 ms 14280 KB Output is correct
20 Correct 598 ms 9928 KB Output is correct
21 Correct 167 ms 5600 KB Output is correct
22 Correct 980 ms 14548 KB Output is correct
23 Correct 844 ms 13512 KB Output is correct
24 Correct 889 ms 13216 KB Output is correct
25 Correct 937 ms 14280 KB Output is correct
26 Correct 965 ms 14276 KB Output is correct
27 Correct 730 ms 8292 KB Output is correct
28 Correct 880 ms 16060 KB Output is correct
29 Correct 2068 ms 72272 KB Output is correct
30 Execution timed out 3062 ms 138640 KB Time limit exceeded
31 Halted 0 ms 0 KB -