oj.uz

Submission #46666

# Submission time Handle Problem Language Result Execution time Memory
46666 2018-04-22T14:10:58 Z qoo2p5 Soccer (JOI17_soccer) C++17
100 / 100
 697 ms 39736 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF = (int) 1e9 + 1e6 + 123;
const ll LINF = (ll) 1e18 + 1e9 + 123;

#define rep(i, s, t) for (auto i = (s); i < (t); ++(i))
#define per(i, s, t) for (auto i = (s); i >= (t); --(i))
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define mp make_pair
#define pb push_back

bool mini(auto &x, const auto &y) {
    if (y < x) {
        x = y;
        return 1;
    }
    return 0;
}

bool maxi(auto &x, const auto &y) {
    if (y > x) {
        x = y;
        return 1;
    }
    return 0;
}

void run();

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    run();
    return 0;
}

const int N = (int) 1e5 + 123;
const int K = 505;

int h, w;
ll a, b, c;
int n;
int x[N], y[N];
int dist[K][K];
ll dp[K][K][6];
bool vis[K][K][6];

const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};

struct V {
    int i, j, t;
    
    bool operator<(const V &b) const {
        return mp(i, mp(j, t)) < mp(b.i, mp(b.j, b.t));
    }
};

void run() {
    cin >> h >> w;
    cin >> a >> b >> c;
    cin >> n;
    rep(i, 0, n) {
        cin >> x[i] >> y[i];
        x[i]++;
        y[i]++;
    }
    
    {
        queue<pair<int, int>> q;
        rep(i, 0, K) rep(j, 0, K) dist[i][j] = INF;
        rep(i, 0, n) {
            q.push({x[i], y[i]});
            dist[x[i]][y[i]] = 0;
        }
        while (sz(q)) {
            auto v = q.front();
            q.pop();
            rep(dir, 0, 4) {
                int nx = v.first + dx[dir];
                int ny = v.second + dy[dir];
                if (0 <= nx && nx < K && 0 <= ny && ny < K && mini(dist[nx][ny], dist[v.first][v.second] + 1)) {
                    q.push({nx, ny});
                }
            }
        }
    }
    
    rep(i, 1, K - 1) {
        rep(j, 1, K - 1) {
            
        }
    }
    
    rep(i, 0, K) rep(j, 0, K) rep(t, 0, 6) {
        dp[i][j][t] = LINF * (i != 0 && i != K - 1) * (j != 0 && j != K - 1);
    }
    dp[x[0]][y[0]][1] = 0;
    priority_queue<pair<ll, V>> q;
    q.push({0, {x[0], y[0], 1}});
    
    while (sz(q)) {
        V v = q.top().second;
        q.pop();
        if (vis[v.i][v.j][v.t]) {
            continue;
        }
        vis[v.i][v.j][v.t] = 1;
        
        if (v.t == 0) {
            if (mini(dp[v.i][v.j][1], dp[v.i][v.j][0] + dist[v.i][v.j] * c)) {
                q.push({-dp[v.i][v.j][1], {v.i, v.j, 1}});
            }
        } else if (v.t == 1) {
            rep(dir, 0, 4) {
                if (mini(dp[v.i][v.j][2 + dir], dp[v.i][v.j][1] + b)) {
                    q.push({-dp[v.i][v.j][2 + dir], {v.i, v.j, 2 + dir}});
                }
                int ni = v.i + dx[dir];
                int nj = v.j + dy[dir];
                if (mini(dp[ni][nj][1], dp[v.i][v.j][1] + c)) {
                    q.push({-dp[ni][nj][1], {ni, nj, 1}});
                }
            }
            if (mini(dp[v.i][v.j][0], dp[v.i][v.j][v.t])) {
                q.push({-dp[v.i][v.j][0], {v.i, v.j, 0}});
            }
        } else {
            int dir = v.t - 2;
            int ni = v.i + dx[dir];
            int nj = v.j + dy[dir];
            if (mini(dp[ni][nj][v.t], dp[v.i][v.j][v.t] + a)) {
                q.push({-dp[ni][nj][v.t], {ni, nj, v.t}});
            }
            if (mini(dp[v.i][v.j][0], dp[v.i][v.j][v.t])) {
                q.push({-dp[v.i][v.j][0], {v.i, v.j, 0}});
            }
        }
    }
    
    cout << dp[x[n - 1]][y[n - 1]][0] << "\n";
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 571 ms 21088 KB Output is correct
2 Correct 528 ms 39736 KB Output is correct
3 Correct 502 ms 39736 KB Output is correct
4 Correct 536 ms 39736 KB Output is correct
5 Correct 310 ms 39736 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 585 ms 39736 KB Output is correct
2 Correct 551 ms 39736 KB Output is correct
3 Correct 525 ms 39736 KB Output is correct
4 Correct 438 ms 39736 KB Output is correct
5 Correct 531 ms 39736 KB Output is correct
6 Correct 423 ms 39736 KB Output is correct
7 Correct 528 ms 39736 KB Output is correct
8 Correct 491 ms 39736 KB Output is correct
9 Correct 570 ms 39736 KB Output is correct
10 Correct 540 ms 39736 KB Output is correct
11 Correct 527 ms 39736 KB Output is correct
12 Correct 527 ms 39736 KB Output is correct
13 Correct 415 ms 39736 KB Output is correct
14 Correct 540 ms 39736 KB Output is correct
15 Correct 518 ms 39736 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 571 ms 21088 KB Output is correct
2 Correct 528 ms 39736 KB Output is correct
3 Correct 502 ms 39736 KB Output is correct
4 Correct 536 ms 39736 KB Output is correct
5 Correct 310 ms 39736 KB Output is correct
6 Correct 585 ms 39736 KB Output is correct
7 Correct 551 ms 39736 KB Output is correct
8 Correct 525 ms 39736 KB Output is correct
9 Correct 438 ms 39736 KB Output is correct
10 Correct 531 ms 39736 KB Output is correct
11 Correct 423 ms 39736 KB Output is correct
12 Correct 528 ms 39736 KB Output is correct
13 Correct 491 ms 39736 KB Output is correct
14 Correct 570 ms 39736 KB Output is correct
15 Correct 540 ms 39736 KB Output is correct
16 Correct 527 ms 39736 KB Output is correct
17 Correct 527 ms 39736 KB Output is correct
18 Correct 415 ms 39736 KB Output is correct
19 Correct 540 ms 39736 KB Output is correct
20 Correct 518 ms 39736 KB Output is correct
21 Correct 425 ms 39736 KB Output is correct
22 Correct 680 ms 39736 KB Output is correct
23 Correct 676 ms 39736 KB Output is correct
24 Correct 692 ms 39736 KB Output is correct
25 Correct 549 ms 39736 KB Output is correct
26 Correct 591 ms 39736 KB Output is correct
27 Correct 414 ms 39736 KB Output is correct
28 Correct 402 ms 39736 KB Output is correct
29 Correct 559 ms 39736 KB Output is correct
30 Correct 325 ms 39736 KB Output is correct
31 Correct 554 ms 39736 KB Output is correct
32 Correct 697 ms 39736 KB Output is correct
33 Correct 454 ms 39736 KB Output is correct
34 Correct 677 ms 39736 KB Output is correct
35 Correct 333 ms 39736 KB Output is correct