Submission #1066262

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066262		sammyuri	Soccer (JOI17_soccer)	C++17	35 / 100	3025 ms	21492 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 int pack(pair<int, int> xx) {
    return 1000 * xx.first + xx.second;
}
inline pair<int, int> unpack(int xx) {
    return {xx / 1000, xx % 1000};
}

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

Compilation message (stderr)

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

• Subtask 1: 5 / 5
• Subtask 2: 30 / 30
• Subtask 3: 0 / 65