oj.uz

Submission #1066262

# Submission time Handle Problem Language Result Execution time Memory
1066262 2024-08-19T17:10:48 Z sammyuri Soccer (JOI17_soccer) C++17
35 / 100
 3000 ms 21492 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 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

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

# Verdict Execution time Memory Grader output
1 Correct 168 ms 8024 KB Output is correct
2 Correct 2 ms 4188 KB Output is correct
3 Correct 949 ms 19984 KB Output is correct
4 Correct 1646 ms 20048 KB Output is correct
5 Correct 194 ms 10184 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1113 ms 20136 KB Output is correct
2 Correct 1131 ms 20048 KB Output is correct
3 Correct 758 ms 16472 KB Output is correct
4 Correct 848 ms 20312 KB Output is correct
5 Correct 818 ms 16980 KB Output is correct
6 Correct 921 ms 20148 KB Output is correct
7 Correct 1125 ms 20172 KB Output is correct
8 Correct 1078 ms 20052 KB Output is correct
9 Correct 1016 ms 20304 KB Output is correct
10 Correct 98 ms 7004 KB Output is correct
11 Correct 1103 ms 20052 KB Output is correct
12 Correct 1055 ms 20156 KB Output is correct
13 Correct 639 ms 16988 KB Output is correct
14 Correct 1043 ms 20168 KB Output is correct
15 Correct 770 ms 17036 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 8024 KB Output is correct
2 Correct 2 ms 4188 KB Output is correct
3 Correct 949 ms 19984 KB Output is correct
4 Correct 1646 ms 20048 KB Output is correct
5 Correct 194 ms 10184 KB Output is correct
6 Correct 1113 ms 20136 KB Output is correct
7 Correct 1131 ms 20048 KB Output is correct
8 Correct 758 ms 16472 KB Output is correct
9 Correct 848 ms 20312 KB Output is correct
10 Correct 818 ms 16980 KB Output is correct
11 Correct 921 ms 20148 KB Output is correct
12 Correct 1125 ms 20172 KB Output is correct
13 Correct 1078 ms 20052 KB Output is correct
14 Correct 1016 ms 20304 KB Output is correct
15 Correct 98 ms 7004 KB Output is correct
16 Correct 1103 ms 20052 KB Output is correct
17 Correct 1055 ms 20156 KB Output is correct
18 Correct 639 ms 16988 KB Output is correct
19 Correct 1043 ms 20168 KB Output is correct
20 Correct 770 ms 17036 KB Output is correct
21 Correct 169 ms 10072 KB Output is correct
22 Correct 1511 ms 20052 KB Output is correct
23 Correct 1435 ms 18584 KB Output is correct
24 Correct 1376 ms 20048 KB Output is correct
25 Correct 1238 ms 20204 KB Output is correct
26 Correct 1526 ms 20260 KB Output is correct
27 Correct 793 ms 21196 KB Output is correct
28 Correct 1261 ms 21492 KB Output is correct
29 Execution timed out 3025 ms 21452 KB Time limit exceeded
30 Halted 0 ms 0 KB -