Submission #143351

#	Time	Username	Problem	Language	Result	Execution time	Memory
143351		osaaateiasavtnl	Soccer (JOI17_soccer)	C++14	100 / 100	374 ms	24752 KiB

soccer

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
#define x first
#define y second
const int N = 507, INF = 1e18 + 7, MAXP = 1e5 + 7;
struct State {
    int x, y, k, c; bool t;
    bool const operator < (const State s) const { return c > s.c; }
};
vector <ii> v = { {0, -1}, {0, 1}, {-1, 0}, {1, 0} };
int n, m, A, B, C, P;
bool check(int i, int j) { return 0 <= i && 0 <= j && i <= n && j <= m; }
bool us[N][N]; int dist[N][N];
void bfs() {
    queue <ii> q;
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= m; ++j) {
            dist[i][j] = INF;
            if (us[i][j]) { dist[i][j] = 0; q.push({i, j}); }
        }
    }
    while (q.size()) {
        auto p = q.front(); q.pop();
        for (auto e : v) {
            if (check(p.x + e.x, p.y + e.y) && dist[p.x][p.y] + 1 < dist[p.x + e.x][p.y + e.y]) {
                dist[p.x + e.x][p.y + e.y] = dist[p.x][p.y] + 1;
                q.push({p.x + e.x, p.y + e.y});
            }
        }
    }
}
priority_queue <State> mq;
ii f[MAXP];
int dp1[N][N][4], dp2[N][N];
void upd(int x, int y, int k, int c) {
    if (check(x, y) && c < dp1[x][y][k]) {
        dp1[x][y][k] = c;
        mq.push({x, y, k, dp1[x][y][k], 0});
    }
}
void upd(int x, int y, int c) {
    if (check(x, y) && c < dp2[x][y]) {
        dp2[x][y] = c;
        mq.push({x, y, -1, dp2[x][y], 1});
    }
}
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    cin >> n >> m >> A >> B >> C >> P;  
    for (int i = 0; i < P; ++i) { int x, y; cin >> x >> y; us[x][y] = 1; f[i] = {x, y}; }
    bfs();
    for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) for (int k = 0; k < 4; ++k) dp1[i][j][k] = INF;
    for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) dp2[i][j] = INF;
    upd(f[0].x, f[0].y, 0);
    while (mq.size()) {
        auto s = mq.top(); mq.pop();
        if (s.x == f[P - 1].x && s.y == f[P - 1].y) { cout << s.c << '\n'; exit(0); }
        if (s.t) {
            for (auto e : v) upd(s.x + e.x, s.y + e.y, s.c + C);
            for (int i = 0; i < 4; ++i) upd(s.x, s.y, i, s.c + B);
        }
        else {
            upd(s.x, s.y, s.c + C * dist[s.x][s.y]);
            upd(s.x + v[s.k].x, s.y + v[s.k].y, s.k, s.c + A);   
        }
    }
}

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