oj.uz

Submission #114195

# Submission time Handle Problem Language Result Execution time Memory
114195 2019-05-31T09:04:39 Z popovicirobert Soccer (JOI17_soccer) C++14
35 / 100
 1594 ms 262144 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});
            }
        }

    }
}

struct Data {
    int l, c;
    ll cst;

    bool operator <(const Data &other) const {
        return cst > other.cst;
    }
};

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

    priority_queue <Data> pq;

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

    while(pq.size()) {
        auto cur = pq.top();
        pq.pop();

        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) {
                dst[l][c] = cur.cst + C;
                pq.push({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) {
                dst[i][cur.c] = cst;
                pq.push({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) {
                dst[cur.l][i] = cst;
                pq.push({cur.l, i, cst});
            }
        }
    }

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

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 2552 KB Output is correct
2 Correct 4 ms 768 KB Output is correct
3 Correct 1303 ms 8588 KB Output is correct
4 Correct 1440 ms 8676 KB Output is correct
5 Correct 313 ms 4072 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1297 ms 8552 KB Output is correct
2 Correct 1418 ms 8680 KB Output is correct
3 Correct 930 ms 7780 KB Output is correct
4 Correct 1239 ms 8676 KB Output is correct
5 Correct 1033 ms 7784 KB Output is correct
6 Correct 1174 ms 8676 KB Output is correct
7 Correct 1306 ms 8664 KB Output is correct
8 Correct 1394 ms 8680 KB Output is correct
9 Correct 1375 ms 8656 KB Output is correct
10 Correct 123 ms 2296 KB Output is correct
11 Correct 1401 ms 8676 KB Output is correct
12 Correct 1594 ms 8552 KB Output is correct
13 Correct 907 ms 7784 KB Output is correct
14 Correct 1337 ms 8544 KB Output is correct
15 Correct 977 ms 7796 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 2552 KB Output is correct
2 Correct 4 ms 768 KB Output is correct
3 Correct 1303 ms 8588 KB Output is correct
4 Correct 1440 ms 8676 KB Output is correct
5 Correct 313 ms 4072 KB Output is correct
6 Correct 1297 ms 8552 KB Output is correct
7 Correct 1418 ms 8680 KB Output is correct
8 Correct 930 ms 7780 KB Output is correct
9 Correct 1239 ms 8676 KB Output is correct
10 Correct 1033 ms 7784 KB Output is correct
11 Correct 1174 ms 8676 KB Output is correct
12 Correct 1306 ms 8664 KB Output is correct
13 Correct 1394 ms 8680 KB Output is correct
14 Correct 1375 ms 8656 KB Output is correct
15 Correct 123 ms 2296 KB Output is correct
16 Correct 1401 ms 8676 KB Output is correct
17 Correct 1594 ms 8552 KB Output is correct
18 Correct 907 ms 7784 KB Output is correct
19 Correct 1337 ms 8544 KB Output is correct
20 Correct 977 ms 7796 KB Output is correct
21 Runtime error 664 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
22 Halted 0 ms 0 KB -