oj.uz

Submission #1066256

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

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

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 8196 KB Output is correct
2 Correct 1 ms 4184 KB Output is correct
3 Correct 1062 ms 20120 KB Output is correct
4 Correct 1628 ms 20300 KB Output is correct
5 Correct 221 ms 10076 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1301 ms 19984 KB Output is correct
2 Correct 1279 ms 19924 KB Output is correct
3 Correct 881 ms 16824 KB Output is correct
4 Correct 1040 ms 20048 KB Output is correct
5 Correct 947 ms 16976 KB Output is correct
6 Correct 1076 ms 20048 KB Output is correct
7 Correct 1270 ms 20136 KB Output is correct
8 Correct 1276 ms 20084 KB Output is correct
9 Correct 1259 ms 20048 KB Output is correct
10 Correct 131 ms 6744 KB Output is correct
11 Correct 1254 ms 20052 KB Output is correct
12 Correct 1281 ms 20048 KB Output is correct
13 Correct 801 ms 16820 KB Output is correct
14 Correct 1283 ms 20048 KB Output is correct
15 Correct 936 ms 16976 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 8196 KB Output is correct
2 Correct 1 ms 4184 KB Output is correct
3 Correct 1062 ms 20120 KB Output is correct
4 Correct 1628 ms 20300 KB Output is correct
5 Correct 221 ms 10076 KB Output is correct
6 Correct 1301 ms 19984 KB Output is correct
7 Correct 1279 ms 19924 KB Output is correct
8 Correct 881 ms 16824 KB Output is correct
9 Correct 1040 ms 20048 KB Output is correct
10 Correct 947 ms 16976 KB Output is correct
11 Correct 1076 ms 20048 KB Output is correct
12 Correct 1270 ms 20136 KB Output is correct
13 Correct 1276 ms 20084 KB Output is correct
14 Correct 1259 ms 20048 KB Output is correct
15 Correct 131 ms 6744 KB Output is correct
16 Correct 1254 ms 20052 KB Output is correct
17 Correct 1281 ms 20048 KB Output is correct
18 Correct 801 ms 16820 KB Output is correct
19 Correct 1283 ms 20048 KB Output is correct
20 Correct 936 ms 16976 KB Output is correct
21 Correct 213 ms 10072 KB Output is correct
22 Correct 1642 ms 20052 KB Output is correct
23 Correct 1547 ms 18500 KB Output is correct
24 Correct 1558 ms 20156 KB Output is correct
25 Correct 1414 ms 20156 KB Output is correct
26 Correct 1700 ms 19980 KB Output is correct
27 Correct 1010 ms 20676 KB Output is correct
28 Correct 1441 ms 20956 KB Output is correct
29 Execution timed out 3041 ms 20932 KB Time limit exceeded
30 Halted 0 ms 0 KB -