Submission #755552

#	Time	Username	Problem	Language	Result	Execution time	Memory
755552		PixelCat	Soccer (JOI17_soccer)	C++14	100 / 100	598 ms	66712 KiB

soccer

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
#define int LL
#define INF (int)(1e18)
using namespace std;
using LL = long long;
using pii = pair<int, int>;

void chmin(int &x, int a) {
    x = min(x, a);
}
void chmax(int &x, int a) {
    x = max(x, a);
}

#define inside(x, y) ((x) >= 0 && (x) <= h && (y) >= 0 && (y) <= w)

const int MAXN = 510;
                         // 3  4  5  6
                         // >  <  v  ^
const int dx[7] = {0, 0, 0, 0, 0, 1, -1};
const int dy[7] = {0, 0, 0, 1, -1, 0, 0};
int cost[MAXN][MAXN][3][7];
int dist[MAXN][MAXN][3];
bool vis[MAXN][MAXN][3];

pair<pii, pii> get_players(int h, int w, int n) {
    For(i, 0, h) For(j, 0, w) {
        dist[i][j][0] = -1;
    }
    queue<pii> que;
    pii s, e;
    For(i, 1, n) {
        int x, y; cin >> x >> y;
        que.emplace(x, y);
        dist[x][y][0] = 0;
        if(i == 1) s = pii(x, y);
        else if(i == n) e = pii(x, y);
    }
    while(!que.empty()) {
        pii cur = que.front(); que.pop();
        For(it, 3, 6) {
            int nx = cur.F + dx[it];
            int ny = cur.S + dy[it];
            if(inside(nx, ny) && dist[nx][ny][0] == -1) {
                dist[nx][ny][0] = dist[cur.F][cur.S][0] + 1;
                que.emplace(nx, ny);
            }
        }
    }
    return make_pair(s, e);
}

struct Path {
    int x, y, m, d;
    Path() {}
    Path(int _x, int _y, int _m, int _d):
        x(_x), y(_y), m(_m), d(_d) {}
};
bool operator<(const Path &p1, const Path &p2) {
    return p1.d > p2.d;
}
ostream& operator<<(ostream& os, const Path &p) {
    os << "(" << p.x << ", " << p.y << ", " << p.m << ") = " << p.d;
    return os;
}
// Path src[MAXN][MAXN][3];

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    // =^-w-^=
    int h, w; cin >> h >> w;
    int a, b, c; cin >> a >> b >> c;
    int n; cin >> n;
    pii s, e;
    tie(s, e) = get_players(h, w, n);

    // build graph
    // ball movement
    For(i, 0, h) For(j, 0, w) {
        For(x, 0, 2) For(y, 0, 6) cost[i][j][x][y] = INF;
        For(x, 3, 6) {
            cost[i][j][0][x] = c;
            if(x <= 4) cost[i][j][1][x] = a;
            if(x >= 5) cost[i][j][2][x] = a;
        }
    }
    // 'mode' switching
    For(i, 0, h) For(j, 0, w) {
        int d = dist[i][j][0] * c;
        For(x, 0, 2) For(y, 0, 2) if(x != y) {
            cost[i][j][x][y] = (x == 0 ? 0 : d) + (y == 0 ? 0 : b);
        }
    }
    
    For(i, 0, h) For(j, 0, w) For(m, 0, 2) {
        dist[i][j][m] = INF;
        vis[i][j][m] = false;
    }
    // dijkstra
    priority_queue<Path> pq;
    auto push = [&](int x, int y, int m, int d, const Path &p) {
        if(inside(x, y) && dist[x][y][m] > d) {
            dist[x][y][m] = d;
            // src[x][y][m] = p;
            pq.emplace(Path(x, y, m, d));
        }
    };
    push(s.F, s.S, 0, 0, Path(0, 0, 0, 0));
    while(!pq.empty()) {
        Path p = pq.top(); pq.pop();
        if(vis[p.x][p.y][p.m]) continue;
        vis[p.x][p.y][p.m] = true;

        For(m2, 0, 2) push(p.x, p.y, m2, p.d + cost[p.x][p.y][p.m][m2], p);
        For(dir, 3, 6) {
            int nx = p.x + dx[dir];
            int ny = p.y + dy[dir];
            push(nx, ny, p.m, p.d + cost[p.x][p.y][p.m][dir], p);
        }
    }

    int ans = INF;
    For(m, 0, 2) chmin(ans, dist[e.F][e.S][m]);
    cout << ans << "\n";

    // cerr << dist[1][4][0] << "\n";
    // cerr << dist[1][5][0] << "\n";
    // int m = -1;
    // For(m2, 0, 2) if(ans == dist[e.F][e.S][m2]) m = m2;
    // Path p(e.F, e.S, m, ans);
    // while(p.x != s.F || p.y != s.S) {
    //     cerr << p << "\n";
    //     p = src[p.x][p.y][p.m];
    // }
    return 0;
}

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