Submission #837330

#	Time	Username	Problem	Language	Result	Execution time	Memory
837330		_martynas	Soccer (JOI17_soccer)	C++11	100 / 100	344 ms	22660 KiB

soccer

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int mxh = 505;
const int mxn = 1e5+5;
const ll inf = 1e17;

int h, w, n;
ll A, B, C;
ll s[mxn], t[mxn];
ll dist[mxh][mxh][5]; // 4 - with player, 0-3 - directions
int closest[mxh][mxh];
int diri[4] = {0, 1, 0, -1};
int dirj[4] = {1, 0, -1, 0};

struct Info {
    ll d, i, j, k;
    bool operator<(const Info& other) const {
        return d > other.d;
    }
};

bool in(int i, int j) {
    return i >= 0 && i < h && j >= 0 && j < w;
}

void bfs() {
    queue<pair<int, int>> q;
    vector<vector<bool>> visited(h, vector<bool>(w));
    for(int i = 0; i < n; i++) {
        visited[s[i]][t[i]] = true;
        closest[s[i]][t[i]] = 0;
        q.push({s[i], t[i]});
    }
    while(!q.empty()) {
        int i = q.front().first;
        int j = q.front().second;
        q.pop();
        for(int d = 0; d < 4; d++) {
            int ni = i+diri[d], nj = j+dirj[d];
            if(in(ni, nj) && !visited[ni][nj]) {
                closest[ni][nj] = closest[i][j]+1;
                visited[ni][nj] = true;
                q.push({ni, nj});
            }
        }
    }
}

int main(int argc, char const *argv[]) {
    cin >> h >> w >> A >> B >> C; h++, w++;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> s[i] >> t[i];
    if(C <= A) {
        cout << C*(labs(s[0]-s[n-1])+labs(t[0]-t[n-1])) << "\n";
        return 0;
    }
    for(int i = 0; i < h; i++) {
        for(int j = 0; j < w; j++) {
            for(int k = 0; k < 5; k++) dist[i][j][k] = inf;
        }
    }
    bfs();
    priority_queue<Info> pq;
    dist[s[0]][t[0]][4] = 0;
    pq.push(Info{dist[s[0]][t[0]][4], s[0], t[0], 4});
    while(!pq.empty()) {
        Info c = pq.top();
        pq.pop();
        if(dist[c.i][c.j][c.k] != c.d) continue;
        // cout << c.i << " " << c.j << " " << c.k << ": " << c.d << "\n";
        if(c.k == 4) {
            // ball with a player
            // walk again
            for(int d = 0; d < 4; d++) {
                int ni = c.i+diri[d], nj = c.j+dirj[d];
                if(in(ni, nj) && dist[ni][nj][4] > c.d+C) {
                    dist[ni][nj][4] = c.d+C;
                    // printf("push: %lld %d %d %d\n", dist[ni][nj][4], ni, nj, 4);
                    pq.push(Info{dist[ni][nj][4], ni, nj, 4});
                }
            }
            // kick the ball
            for(int d = 0; d < 4; d++) {
                int ni = c.i+diri[d], nj = c.j+dirj[d];
                if(in(ni, nj) && dist[ni][nj][d] > c.d+A+B) {
                    dist[ni][nj][d] = c.d+A+B;
                    // printf("push: %lld %d %d %d\n", dist[ni][nj][d], ni, nj, d);
                    pq.push(Info{dist[ni][nj][d], ni, nj, d});
                }
            }
        }
        else {
            // ball w/o a player
            // continue flying
            int ni = c.i+diri[c.k], nj = c.j+dirj[c.k];
            if(in(ni, nj) && dist[ni][nj][c.k] > c.d+A) {
                dist[ni][nj][c.k] = c.d+A;
                // printf("push: %lld %d %d %d\n", dist[ni][nj][c.k], ni, nj, c.k);
                pq.push(Info{dist[ni][nj][c.k], ni, nj, c.k});
            }
            // find closest player to kick
            if(dist[c.i][c.j][4] > c.d+C*closest[c.i][c.j]) {
                dist[c.i][c.j][4] = c.d+C*closest[c.i][c.j];
                pq.push(Info{dist[c.i][c.j][4], c.i, c.j, 4});
            }
        }
    }
    ll ans = inf;
    for(int k = 0; k < 5; k++) ans = min(ans, dist[s[n-1]][t[n-1]][k]);
    cout << ans << "\n";
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 30 / 30
• Subtask 3: 65 / 65