Submission #1066324

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066324		sammyuri	Soccer (JOI17_soccer)	C++17	35 / 100	3053 ms	16844 KiB

soccer

#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}};
}
set<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.insert(pack({curdist, {i, j}}));
        }
    ll best = 1e18;
    while (pq.size()) {
        auto cur = unpack(*pq.begin());
        pq.erase(pq.begin());
        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) {
                pq.erase(pack({dist_2[ii][j], {ii, j}}));
                dist_2[ii][j] = newdist;
                pq.insert(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) {
                pq.erase(pack({dist_2[i][jj], {i, jj}}));
                dist_2[i][jj] = newdist;
                pq.insert(pack({newdist, {i, jj}}));
            }
        }
    }
    cout << best << endl;
    return 0;
}

Compilation message (stderr)

soccer.cpp: In function 'int main()':
soccer.cpp:90:67: warning: 'endj' may be used uninitialized in this function [-Wmaybe-uninitialized]
   90 |         best = min(best, curdist + calc_cost(abs(i - endi), abs(j - endj)));
      |                                                                 ~~^~~~~~
soccer.cpp:90:52: warning: 'endi' may be used uninitialized in this function [-Wmaybe-uninitialized]
   90 |         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 / 5
• Subtask 2: 30 / 30
• Subtask 3: 0 / 65