oj.uz

Submission #1066324

# Submission time Handle Problem Language Result Execution time Memory
1066324 2024-08-19T17:56:59 Z sammyuri Soccer (JOI17_soccer) C++17
35 / 100
 3000 ms 16844 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}};
}
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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 7260 KB Output is correct
2 Correct 1 ms 4188 KB Output is correct
3 Correct 832 ms 16212 KB Output is correct
4 Correct 1330 ms 16220 KB Output is correct
5 Correct 179 ms 8540 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 991 ms 16392 KB Output is correct
2 Correct 1060 ms 16220 KB Output is correct
3 Correct 690 ms 13864 KB Output is correct
4 Correct 808 ms 16220 KB Output is correct
5 Correct 740 ms 13652 KB Output is correct
6 Correct 826 ms 16228 KB Output is correct
7 Correct 1051 ms 16232 KB Output is correct
8 Correct 998 ms 16048 KB Output is correct
9 Correct 987 ms 16212 KB Output is correct
10 Correct 97 ms 6236 KB Output is correct
11 Correct 1008 ms 16232 KB Output is correct
12 Correct 1027 ms 16216 KB Output is correct
13 Correct 612 ms 13660 KB Output is correct
14 Correct 990 ms 16228 KB Output is correct
15 Correct 755 ms 13880 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 7260 KB Output is correct
2 Correct 1 ms 4188 KB Output is correct
3 Correct 832 ms 16212 KB Output is correct
4 Correct 1330 ms 16220 KB Output is correct
5 Correct 179 ms 8540 KB Output is correct
6 Correct 991 ms 16392 KB Output is correct
7 Correct 1060 ms 16220 KB Output is correct
8 Correct 690 ms 13864 KB Output is correct
9 Correct 808 ms 16220 KB Output is correct
10 Correct 740 ms 13652 KB Output is correct
11 Correct 826 ms 16228 KB Output is correct
12 Correct 1051 ms 16232 KB Output is correct
13 Correct 998 ms 16048 KB Output is correct
14 Correct 987 ms 16212 KB Output is correct
15 Correct 97 ms 6236 KB Output is correct
16 Correct 1008 ms 16232 KB Output is correct
17 Correct 1027 ms 16216 KB Output is correct
18 Correct 612 ms 13660 KB Output is correct
19 Correct 990 ms 16228 KB Output is correct
20 Correct 755 ms 13880 KB Output is correct
21 Correct 166 ms 8540 KB Output is correct
22 Correct 1343 ms 16216 KB Output is correct
23 Correct 1303 ms 15044 KB Output is correct
24 Correct 1237 ms 16244 KB Output is correct
25 Correct 1162 ms 16468 KB Output is correct
26 Correct 1394 ms 16212 KB Output is correct
27 Correct 752 ms 16772 KB Output is correct
28 Correct 1134 ms 16836 KB Output is correct
29 Execution timed out 3053 ms 16844 KB Time limit exceeded
30 Halted 0 ms 0 KB -