oj.uz

Submission #114202

# Submission time Handle Problem Language Result Execution time Memory
114202 2019-05-31T09:18:01 Z popovicirobert Soccer (JOI17_soccer) C++14
0 / 100
 3000 ms 6464 KB 
#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});
            }
        }

    }
}


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> > inq(h + 1, vector <bool>(w + 1, 0));

    queue < pair <int, int> > Q;

    Q.push({x[1], y[1]});
    dst[x[1]][y[1]] = 0;

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

        inq[cur.first][cur.second] = 0;

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

            if(in(l, c) && dst[l][c] > dst[cur.first][cur.second] + C) {
                dst[l][c] = dst[cur.first][cur.second] + C;
                if(inq[l][c] == 0) {
                    inq[l][c] = 1;
                    Q.push({l, c});
                }
            }
        }

        for(i = 0; i <= h; i++) {
            int l = i, c = cur.second;
            ll cst = dst[cur.first][cur.second] + 1LL * A * abs(cur.first - i) + B;

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

            if(dst[l][c] > cst) {
                dst[l][c] = cst;
                if(inq[l][c] == 0) {
                    inq[l][c] = 1;
                    Q.push({l, c});
                }
            }
        }

        for(i = 0; i <= w; i++) {
            int l = cur.first, c = i;
            ll cst = dst[cur.first][cur.second] + 1LL * A * abs(cur.second - i) + B;

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

            if(dst[l][c] > cst) {
                dst[l][c] = cst;
                if(inq[l][c] == 0) {
                    inq[l][c] = 1;
                    Q.push({l, c});
                }
            }
        }
    }

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

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3054 ms 1792 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3036 ms 6464 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3054 ms 1792 KB Time limit exceeded
2 Halted 0 ms 0 KB -