oj.uz

답안 #1066259

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1066259 2024-08-19T17:08:20 Z sammyuri Soccer (JOI17_soccer) C++17
35 / 100
 3000 ms 20944 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;
}

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, 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:81:67: warning: 'endj' may be used uninitialized in this function [-Wmaybe-uninitialized]
   81 |         best = min(best, curdist + calc_cost(abs(i - endi), abs(j - endj)));
      |                                                                 ~~^~~~~~
soccer.cpp:81:52: warning: 'endi' may be used uninitialized in this function [-Wmaybe-uninitialized]
   81 |         best = min(best, curdist + calc_cost(abs(i - endi), abs(j - endj)));
      |                                                  ~~^~~~~~
soccer.cpp:27:17: warning: 'startj' may be used uninitialized in this function [-Wmaybe-uninitialized]
   27 |     int starti, startj, endi, endj;
      |                 ^~~~~~
soccer.cpp:27:9: warning: 'starti' may be used uninitialized in this function [-Wmaybe-uninitialized]
   27 |     int starti, startj, endi, endj;
      |         ^~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 141 ms 8028 KB Output is correct
2 Correct 1 ms 4184 KB Output is correct
3 Correct 839 ms 20028 KB Output is correct
4 Correct 1417 ms 20004 KB Output is correct
5 Correct 167 ms 10072 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1006 ms 20052 KB Output is correct
2 Correct 1014 ms 20152 KB Output is correct
3 Correct 701 ms 17012 KB Output is correct
4 Correct 798 ms 20052 KB Output is correct
5 Correct 754 ms 16976 KB Output is correct
6 Correct 818 ms 20156 KB Output is correct
7 Correct 982 ms 20048 KB Output is correct
8 Correct 1014 ms 20160 KB Output is correct
9 Correct 968 ms 20052 KB Output is correct
10 Correct 94 ms 6748 KB Output is correct
11 Correct 994 ms 20168 KB Output is correct
12 Correct 1041 ms 20048 KB Output is correct
13 Correct 617 ms 16836 KB Output is correct
14 Correct 1018 ms 20164 KB Output is correct
15 Correct 759 ms 16980 KB Output is correct

Subtask #3
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 141 ms 8028 KB Output is correct
2 Correct 1 ms 4184 KB Output is correct
3 Correct 839 ms 20028 KB Output is correct
4 Correct 1417 ms 20004 KB Output is correct
5 Correct 167 ms 10072 KB Output is correct
6 Correct 1006 ms 20052 KB Output is correct
7 Correct 1014 ms 20152 KB Output is correct
8 Correct 701 ms 17012 KB Output is correct
9 Correct 798 ms 20052 KB Output is correct
10 Correct 754 ms 16976 KB Output is correct
11 Correct 818 ms 20156 KB Output is correct
12 Correct 982 ms 20048 KB Output is correct
13 Correct 1014 ms 20160 KB Output is correct
14 Correct 968 ms 20052 KB Output is correct
15 Correct 94 ms 6748 KB Output is correct
16 Correct 994 ms 20168 KB Output is correct
17 Correct 1041 ms 20048 KB Output is correct
18 Correct 617 ms 16836 KB Output is correct
19 Correct 1018 ms 20164 KB Output is correct
20 Correct 759 ms 16980 KB Output is correct
21 Correct 172 ms 10104 KB Output is correct
22 Correct 1430 ms 20052 KB Output is correct
23 Correct 1399 ms 18512 KB Output is correct
24 Correct 1322 ms 20048 KB Output is correct
25 Correct 1161 ms 20180 KB Output is correct
26 Correct 1466 ms 20048 KB Output is correct
27 Correct 740 ms 20688 KB Output is correct
28 Correct 1156 ms 20944 KB Output is correct
29 Execution timed out 3064 ms 20860 KB Time limit exceeded
30 Halted 0 ms 0 KB -