oj.uz

Submission #755552

# Submission time Handle Problem Language Result Execution time Memory
755552 2023-06-10T10:18:52 Z PixelCat Soccer (JOI17_soccer) C++14
100 / 100
 598 ms 66712 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 18756 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 422 ms 65580 KB Output is correct
4 Correct 412 ms 65580 KB Output is correct
5 Correct 40 ms 21076 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 421 ms 65656 KB Output is correct
2 Correct 413 ms 65652 KB Output is correct
3 Correct 295 ms 55840 KB Output is correct
4 Correct 287 ms 65600 KB Output is correct
5 Correct 273 ms 58652 KB Output is correct
6 Correct 292 ms 65600 KB Output is correct
7 Correct 405 ms 65752 KB Output is correct
8 Correct 343 ms 65696 KB Output is correct
9 Correct 375 ms 65716 KB Output is correct
10 Correct 49 ms 16980 KB Output is correct
11 Correct 353 ms 65712 KB Output is correct
12 Correct 390 ms 65572 KB Output is correct
13 Correct 238 ms 55836 KB Output is correct
14 Correct 354 ms 65680 KB Output is correct
15 Correct 301 ms 58788 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 18756 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 422 ms 65580 KB Output is correct
4 Correct 412 ms 65580 KB Output is correct
5 Correct 40 ms 21076 KB Output is correct
6 Correct 421 ms 65656 KB Output is correct
7 Correct 413 ms 65652 KB Output is correct
8 Correct 295 ms 55840 KB Output is correct
9 Correct 287 ms 65600 KB Output is correct
10 Correct 273 ms 58652 KB Output is correct
11 Correct 292 ms 65600 KB Output is correct
12 Correct 405 ms 65752 KB Output is correct
13 Correct 343 ms 65696 KB Output is correct
14 Correct 375 ms 65716 KB Output is correct
15 Correct 49 ms 16980 KB Output is correct
16 Correct 353 ms 65712 KB Output is correct
17 Correct 390 ms 65572 KB Output is correct
18 Correct 238 ms 55836 KB Output is correct
19 Correct 354 ms 65680 KB Output is correct
20 Correct 301 ms 58788 KB Output is correct
21 Correct 50 ms 20692 KB Output is correct
22 Correct 553 ms 65560 KB Output is correct
23 Correct 459 ms 52532 KB Output is correct
24 Correct 466 ms 57656 KB Output is correct
25 Correct 530 ms 65560 KB Output is correct
26 Correct 462 ms 65964 KB Output is correct
27 Correct 207 ms 50896 KB Output is correct
28 Correct 203 ms 51240 KB Output is correct
29 Correct 398 ms 59556 KB Output is correct
30 Correct 178 ms 50960 KB Output is correct
31 Correct 496 ms 65784 KB Output is correct
32 Correct 598 ms 66712 KB Output is correct
33 Correct 414 ms 65644 KB Output is correct
34 Correct 498 ms 65840 KB Output is correct
35 Correct 162 ms 50216 KB Output is correct