Submission #1066335

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066335		sammyuri	Soccer (JOI17_soccer)	C++17	100 / 100	226 ms	17104 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][5];
ll a, b, c;

inline ll pack(pair<ll, pair<int, pair<int, int>>> xx) {
    return -(xx.second.first + 5ll * (xx.first * 360000ll + (600ll * xx.second.second.first + xx.second.second.second)));
}
inline pair<ll, pair<int, pair<int, int>>> unpack(ll xx) {
    xx = -xx;
    int aa = xx % 5;
    ll k = (xx / 5) % 360000ll;
    return {xx / (5ll * 360000ll), {aa, {k / 600ll, k % 600ll}}};
}
priority_queue<ll> pq;

int ddx[] = {0, 0, 1, -1};
int ddy[] = {1, -1, 0, 0};

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 ++) {
            for (int k = 0; k < 5; k ++)
                dist_2[i][j][k] = 1e18;
            // initial distance
        }
    dist_2[starti][startj][4] = 0;
    pq.push(pack({0, {4, {starti, startj}}}));
    while (pq.size()) {
        auto cur = unpack(pq.top()); pq.pop();
        ll curdist = cur.first;
        int dir = cur.second.first;
        int i = cur.second.second.first, j = cur.second.second.second;
        if (dist_2[i][j][dir] != curdist)
            continue;
        // cout << i << " " << j << " " << dir << " " << curdist << endl;
        // catch
        if (dir != 4) {
            if (dist_2[i][j][4] > curdist + dist[i][j] * c) {
                dist_2[i][j][4] = curdist + dist[i][j] * c;
                pq.push(pack({curdist + dist[i][j] * c, {4, {i, j}}}));
            }
            int ii = i + ddx[dir], jj = j + ddy[dir];
            if (ii >= 0 && jj >= 0 && ii < h && jj < w) {
                if (dist_2[ii][jj][dir] > curdist + a) {
                    dist_2[ii][jj][dir] = curdist + a;
                    pq.push(pack({curdist + a, {dir, {ii, jj}}}));
                }
            }
        }
        // move
        else {
            for (int dd = 0; dd < 4; dd ++) {
                int ii = i + ddx[dd], jj = j + ddy[dd];
                if (ii >= 0 && jj >= 0 && ii < h && jj < w) {
                    if (dist_2[ii][jj][dd] > curdist + a + b) {
                        dist_2[ii][jj][dd] = curdist + a + b;
                        pq.push(pack({curdist + a + b, {dd, {ii, jj}}}));
                    }
                    if (dist_2[ii][jj][4] > curdist + c) {
                        dist_2[ii][jj][4] = curdist + c;
                        pq.push(pack({curdist + c, {4, {ii, jj}}}));
                    }
                }
            }
        }

    }
    cout << dist_2[endi][endj][4] << endl;
    return 0;
}

Compilation message (stderr)

soccer.cpp: In function 'int main()':
soccer.cpp:12:112: warning: 'startj' may be used uninitialized in this function [-Wmaybe-uninitialized]
   12 |     return -(xx.second.first + 5ll * (xx.first * 360000ll + (600ll * xx.second.second.first + xx.second.second.second)));
      |                                                                                               ~~~~~~~~~~~~~~~~~^~~~~~
soccer.cpp:34:17: note: 'startj' was declared here
   34 |     int starti, startj, endi, endj;
      |                 ^~~~~~
soccer.cpp:12:87: warning: 'starti' may be used uninitialized in this function [-Wmaybe-uninitialized]
   12 |     return -(xx.second.first + 5ll * (xx.first * 360000ll + (600ll * xx.second.second.first + xx.second.second.second)));
      |                                                                      ~~~~~~~~~~~~~~~~~^~~~~
soccer.cpp:34:9: note: 'starti' was declared here
   34 |     int starti, startj, endi, endj;
      |         ^~~~~~
soccer.cpp:118:33: warning: 'endj' may be used uninitialized in this function [-Wmaybe-uninitialized]
  118 |     cout << dist_2[endi][endj][4] << endl;
      |                                 ^
soccer.cpp:118:33: warning: 'endi' may be used uninitialized in this function [-Wmaybe-uninitialized]

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