Submission #882952

#	Time	Username	Problem	Language	Result	Execution time	Memory
882952		DAleksa	Soccer (JOI17_soccer)	C++17	100 / 100	590 ms	115636 KiB

soccer

#include <bits/stdc++.h>

using namespace std;

struct node {
    int v;
    long long w;
};

const int N = 1e5 + 20, M = 501;
int H, W;
long long A, B, C;
int n;
int x[N], y[N];

int f(int i, int j, int k) { return i * M * 3 + j * 3 + k; }

int bfsdist[M][M];
bool bfsmark[M][M];

vector<node> g[M * M * 3];
long long dist[M * M * 3];
set<pair<long long, int>> s;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> H >> W >> A >> B >> C >> n;
    for(int i = 0; i <= H; i++) for(int j = 0; j <= W; j++) bfsdist[i][j] = 1e9;
    queue<pair<int, int>> q;
    for(int i = 0; i < n; i++) {
        cin >> x[i] >> y[i];
        bfsdist[x[i]][y[i]] = 0;
        q.push({x[i], y[i]});
        bfsmark[x[i]][y[i]] = true;
    }
    while(!q.empty()) {
        pair<int, int> p = q.front();
        q.pop();
        int i = p.first, j = p.second;
        for(int di = -1; di <= 1; di++) {
            for(int dj = -1; dj <= 1; dj++) {
                if(di == 0 && dj == 0) continue;
                if(di != 0 && dj != 0) continue;
                if(i + di < 0 || i + di > H || j + dj < 0 || j + dj > W) continue;
                if(bfsmark[i + di][j + dj]) continue;
                bfsmark[i + di][j + dj] = true;
                bfsdist[i + di][j + dj] = bfsdist[i][j] + 1;
                q.push({i + di, j + dj});
            }
        }
    }
    for(int i = 0; i <= H; i++) {
        for(int j = 0; j <= W; j++) {
            if(i + 1 <= H) {
                g[f(i, j, 2)].push_back({f(i + 1, j, 2), C});
                g[f(i + 1, j, 2)].push_back({f(i, j, 2), C});
                g[f(i, j, 0)].push_back({f(i + 1, j, 0), A});
                g[f(i + 1, j, 0)].push_back({f(i, j, 0), A});
            }
            if(j + 1 <= W) {
                g[f(i, j, 2)].push_back({f(i, j + 1, 2), C});
                g[f(i, j + 1, 2)].push_back({f(i, j, 2), C});
                g[f(i, j, 1)].push_back({f(i, j + 1, 1), A});
                g[f(i, j + 1, 1)].push_back({f(i, j, 1), A});
            }
            g[f(i, j, 2)].push_back({f(i, j, 0), B});
            g[f(i, j, 2)].push_back({f(i, j, 1), B});
            g[f(i, j, 0)].push_back({f(i, j, 2), C * 1LL * bfsdist[i][j]});
            g[f(i, j, 1)].push_back({f(i, j, 2), C * 1LL * bfsdist[i][j]});
        }
    }
    for(int i = 0; i <= H; i++) for(int j = 0; j <= W; j++) for(int k = 0; k < 3; k++) dist[f(i, j, k)] = 1e18;
    dist[f(x[0], y[0], 2)] = 0;
    s.insert({0, f(x[0], y[0], 2)});
    while(!s.empty()) {
        pair<long long, int> p = *s.begin();
        s.erase(s.begin());
        long long d = p.first;
        int u = p.second;
        for(node v : g[u]) {
            if(dist[u] + v.w < dist[v.v]) {
                dist[v.v] = dist[u] + v.w;
                s.insert({dist[v.v], v.v});
            }
        }
    }
    cout << min({dist[f(x[n - 1], y[n - 1], 0)], dist[f(x[n - 1], y[n - 1], 1)], dist[f(x[n - 1], y[n - 1], 2)]});
    return 0;
}

Compilation message (stderr)

soccer.cpp: In function 'int main()':
soccer.cpp:79:19: warning: unused variable 'd' [-Wunused-variable]
   79 |         long long d = p.first;
      |                   ^

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