oj.uz

Submission #686881

# Submission time Handle Problem Language Result Execution time Memory
686881 2023-01-26T03:24:28 Z JooDdae Soccer (JOI17_soccer) C++17
5 / 100
 210 ms 12608 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll INF = 1e18;
const int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};

int n, m, k, x[100100], y[100100], X[505], Y[505];
ll A, B, C, D[505][505], d[505][505][2];

queue<array<int, 3>> q;
priority_queue<tuple<ll, int, int, int>> pq;

int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m >> A >> B >> C >> k;
    for(int i=1;i<=k;i++) cin >> x[i] >> y[i];

    for(int i=0;i<=n;i++) for(int j=0;j<=m;j++) {
        D[i][j] = d[i][j][0] = d[i][j][1] = INF;
    }

    for(int i=1;i<k;i++) D[x[i]][y[i]] = 0, q.push({0, x[i], y[i]});
    while(!q.empty()) {
        auto [c, x, y] = q.front(); q.pop();
        for(int i=0;i<4;i++) {
            int xx = x+dx[i], yy = y+dy[i];
            if(xx < 0 || yy < 0 || xx > n || yy > m || D[xx][yy] <= c+1) continue;
            D[xx][yy] = c+1, q.push({c+1, xx, yy});
        }
    }

    memset(X, -1, sizeof X), memset(Y, -1, sizeof Y);
    d[x[1]][y[1]][0] = 0, pq.push({0, x[1], y[1], 0});
    while(!pq.empty()) {
        auto [c, x, y, f] = pq.top(); pq.pop();
        if(d[x][y][f] < -c) continue;

        // if(X[x] > -1) {
        //     ll cost = d[x][X[x]][1] + abs(X[x]-y)*A + B;
        //     if(cost < d[x][y][0]) {
        //         d[x][y][0] = cost, pq.push({-cost, x, y, 0});
        //         if(f) pq.push({c, x, y, f});
        //         continue;
        //     }
        // }
        // if(Y[y] > -1) {
        //     ll cost = d[Y[y]][y][1] + abs(Y[y]-x)*A + B;
        //     if(cost < d[x][y][0]) {
        //         d[x][y][0] = cost, pq.push({-cost, x, y, 0});
        //         if(f) pq.push({c, x, y, f});
        //         continue;
        //     }
        // }
        // cout << -c << ' ' << x << ' ' << y << " " << f << endl;

        if(f) {
            if(X[x] < 0) X[x] = y;
            if(Y[y] < 0) Y[y] = x;
        }

        for(int i=0;i<4;i++) {
            int xx = x+dx[i], yy = y+dy[i];
            if(X[xx] < 0 && Y[yy] < 0) continue;
            ll C = min(X[xx] >= 0 ? d[xx][X[xx]][1] + abs(yy-X[xx])*A+B : INF, Y[yy] >= 0 ? d[Y[yy]][yy][1] + abs(xx-Y[yy])*A+B : INF);
            if(xx < 0 || yy < 0 || xx > n || yy > m || d[xx][yy][0] <= C) continue;
            d[xx][yy][0] = C, pq.push({-C, xx, yy, 0});
        }

        if(!f) {
            if(d[x][y][1] > D[x][y]*C-c) d[x][y][1] = D[x][y]*C-c, pq.push({c-D[x][y]*C, x, y, 1});
            continue;
        }

        if(d[x][y][0] > -c) d[x][y][0] = -c, pq.push({c, x, y, 0});
        for(int i=0;i<4;i++) {
            int xx = x+dx[i], yy = y+dy[i];
            if(xx < 0 || yy < 0 || xx > n || yy > m || d[xx][yy][1] <= C-c) continue;
            d[xx][yy][1] = C-c, pq.push({c-C, xx, yy, 1});
        }
    }

    cout << min(d[x[k]][y[k]][0], d[x[k]][y[k]][1]);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 5324 KB Output is correct
2 Correct 4 ms 340 KB Output is correct
3 Correct 170 ms 12556 KB Output is correct
4 Correct 164 ms 12468 KB Output is correct
5 Correct 42 ms 4536 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 12508 KB Output is correct
2 Correct 201 ms 12560 KB Output is correct
3 Correct 153 ms 11316 KB Output is correct
4 Correct 128 ms 12584 KB Output is correct
5 Correct 163 ms 12608 KB Output is correct
6 Incorrect 210 ms 12588 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 5324 KB Output is correct
2 Correct 4 ms 340 KB Output is correct
3 Correct 170 ms 12556 KB Output is correct
4 Correct 164 ms 12468 KB Output is correct
5 Correct 42 ms 4536 KB Output is correct
6 Correct 186 ms 12508 KB Output is correct
7 Correct 201 ms 12560 KB Output is correct
8 Correct 153 ms 11316 KB Output is correct
9 Correct 128 ms 12584 KB Output is correct
10 Correct 163 ms 12608 KB Output is correct
11 Incorrect 210 ms 12588 KB Output isn't correct
12 Halted 0 ms 0 KB -