Submission #114206

#	Time	Username	Problem	Language	Result	Execution time	Memory
114206		popovicirobert	Soccer (JOI17_soccer)	C++14	35 / 100	3098 ms	19932 KiB

soccer

#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44

using namespace std;

const ll INF = 1e18;
vector < vector <ll> > dst_c;

int dl[] = {-1, 0, 1, 0}, dc[] = {0, -1, 0, 1};

vector <int> x, y;
int h, w, A, B, C, n;

inline bool in(int l, int c) {
    return l >= 0 && c >= 0 && l <= h && c <= w;
}

inline void bfs() {
    queue < pair <int, int> > Q;

    dst_c.resize(h + 1, vector <ll>(w + 1, INF));

    for(int i = 1; i < n; i++) {
        dst_c[x[i]][y[i]] = 0;
        Q.push({x[i], y[i]});
    }

    while(Q.size()) {
        auto cur = Q.front();
        Q.pop();

        for(int i = 0; i < 4; i++) {
            int l = cur.first + dl[i];
            int c = cur.second + dc[i];

            if(in(l, c) && dst_c[l][c] == INF) {
                dst_c[l][c] = dst_c[cur.first][cur.second] + C;
                Q.push({l, c});
            }
        }

    }
}

struct Data {
    int l, c;
    ll cst;

    bool operator <(const Data &other) const {
        if(cst == other.cst) {
            if(l == other.l) return c < other.c;
            return l < other.l;
        }
        return cst < other.cst;
    }
};

inline void del(set <Data> &pq, int l, int c, ll cst) {
    auto it = pq.lower_bound({l, c, cst});
    if(it != pq.end() && it -> l == l && it -> c == c) {
        pq.erase(it);
    }
}

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> h >> w >> A >> B >> C >> n;

    x.resize(n + 1), y.resize(n + 1);
    for(i = 1; i <= n; i++) {
        cin >> x[i] >> y[i];
    }

    bfs();

    vector < vector <ll> > dst(h + 1, vector <ll>(w + 1, INF));
    vector < vector <bool> > vis(h + 1, vector <bool>(w + 1, 0));

    set <Data> pq;

    pq.insert({x[1], y[1], 0});
    dst[x[1]][y[1]] = 0;

    while(pq.size()) {
        auto it = pq.begin();
        Data cur = {it -> l, it -> c, it -> cst};
        pq.erase(pq.begin());

        if(vis[cur.l][cur.c]) {
            continue;
        }

        vis[cur.l][cur.c] = 1;

        for(i = 0; i < 4; i++) {
            int l = cur.l + dl[i];
            int c = cur.c + dc[i];

            if(in(l, c) && dst[l][c] > cur.cst + C) {
                del(pq, l, c, dst[l][c]);
                dst[l][c] = cur.cst + C;
                pq.insert({l, c, dst[l][c]});
            }
        }

        for(i = 0; i <= h; i++) {
            ll cst = cur.cst + 1LL * A * abs(i - cur.l) + B;

            if(i != x[n] || cur.c != y[n]) {
                cst += dst_c[i][cur.c];
            }

            if(dst[i][cur.c] > cst) {
                del(pq, i, cur.c, dst[i][cur.c]);
                dst[i][cur.c] = cst;
                pq.insert({i, cur.c, cst});
            }
        }
        for(i = 0; i <= w; i++) {
            ll cst = cur.cst + 1LL * A * abs(i - cur.c) + B;

            if(i != y[n] || cur.l != x[n]) {
                cst += dst_c[cur.l][i];
            }

            if(dst[cur.l][i] > cst) {
                del(pq, cur.l, i, dst[cur.l][i]);
                dst[cur.l][i] = cst;
                pq.insert({cur.l, i, cst});
            }
        }
    }

    cout << dst[x[n]][y[n]];

    //cin.close();
    //cout.close();
    return 0;
}

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