Submission #686881

#	Time	Username	Problem	Language	Result	Execution time	Memory
686881		JooDdae	Soccer (JOI17_soccer)	C++17	5 / 100	210 ms	12608 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];

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 / 5
• Subtask 2: 0 / 30
• Subtask 3: 0 / 65