Submission #686901

#	Time	Username	Problem	Language	Result	Execution time	Memory
686901		JooDdae	Soccer (JOI17_soccer)	C++17	35 / 100	259 ms	12776 KiB

soccer

#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];

vector<int> vx[505], vy[505];

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});
        }
    }

    for(int i=1;i<k;i++) {
        vx[x[i]].push_back(y[i]);
        vy[y[i]].push_back(x[i]);
    }

    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;

        // cout << -c << ' ' << x << ' ' << y << " " << f << endl;

        if(f) {
            if(X[x] < 0) {
                X[x] = y;
                for(auto y : vx[x]) {
                    ll C = abs(y-X[x])*A+B-c;
                    if(C < d[x][y][0]) d[x][y][0] = C, pq.push({-C, x, y, 0});
                }
            }
            if(Y[y] < 0) {
                Y[y] = x;
                for(auto x : vy[y]) {
                    ll C = abs(x-Y[y])*A+B-c;
                    if(C < d[x][y][0]) 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(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 / 5
• Subtask 2: 30 / 30
• Subtask 3: 0 / 65