oj.uz

Submission #651044

# Submission time Handle Problem Language Result Execution time Memory
651044 2022-10-16T15:25:22 Z Ronin13 Soccer (JOI17_soccer) C++14
100 / 100
 651 ms 33564 KB 
#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
#define ull unsigned ll
using namespace std;


pii mov[] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
const int NMAX = 502;
ll d[NMAX][NMAX];
ll D[NMAX][NMAX][4][2];

int main(){
    int h, w; cin >> h >> w;
    ll a, b, c; cin >> a >> b >> c;
    h++; w++;
    int n; cin >> n;
    int x[n + 1], y[n + 1];
    for(int i = 1; i <= n; i++){
        cin >> x[i] >> y[i];
        x[i]++;
        y[i]++;
    }
    for(int i = 1; i <= h; ++i){
        for(int j = 1; j <= w; j++){
            d[i][j] = 1e9;
            for(int x = 0; x < 4; x++){
                for(int y = 0; y < 2; y++) D[i][j][x][y] = 1e18;
            }
        }
    }
    queue <pii> q;
    for(int i = 1; i <= n - 1; i++){
        d[x[i]][y[i]] = 0;
        q.push({x[i], y[i]});
    }
    while(!q.empty()){
        int x = q.front().f, y = q.front().s;
        q.pop();
        if(x > 1 && d[x - 1][y] == 1e9) d[x - 1][y] = d[x][y] + 1, q.push({x - 1, y});
        if(x < h && d[x + 1][y] == 1e9) d[x + 1][y] = d[x][y] + 1, q.push({x + 1, y});
        if(y > 1 && d[x][y - 1] == 1e9) d[x][y - 1] = d[x][y] + 1, q.push({x, y - 1});
        if(y < w && d[x][y + 1] == 1e9) d[x][y + 1] = d[x][y] + 1, q.push({x, y + 1});
     }
     /*for(int i = 1; i <= h; i++){
        for(int j = 1; j <= w; j++) cout << d[i][j] << ' ';
        cout << "\n";
     }*/
    set <pair<ll, pair<pii, pii> > > st;
    D[x[1]][y[1]][0][0] = 0;
    st.insert({0, {{x[1], y[1]}, {0, 0}}});
    while(!st.empty()){
        pair<ll, pair<pii, pii> > cur = *st.begin();
        st.erase(st.begin());
        ll x = cur.s.f.f, y = cur.s.f.s;
        int ind = cur.s.s.s, dir = cur.s.s.f;
        if(ind == 1){
            pii nn = mov[dir];
            int nx = x + nn.f;
            int ny = y + nn.s;
            if(nx > 0 && nx <= h && ny > 0 && ny <= w){
                if(D[nx][ny][dir][ind] > cur.f + a){
                    st.erase({D[nx][ny][dir][ind], {{nx, ny}, {dir, ind}}});
                    D[nx][ny][dir][ind] = cur.f + a;
                    st.insert({D[nx][ny][dir][ind], {{nx, ny}, {dir, ind}}});
                }
            }
            if(D[x][y][0][0] > cur.f + d[x][y] * c){
                st.erase({D[x][y][0][0], {{x, y}, {0, 0}}});
                D[x][y][0][0] = cur.f + d[x][y] * c;
                st.insert({D[x][y][0][0], {{x, y}, {0, 0}}});
            }
        }
        if(ind == 0){
            for(int j = 0; j < 4; j++){
                int nx = x + mov[j].f, ny = y + mov[j].s;
                if(nx > 0 && nx <= h && ny > 0 && ny <= w){
                    if(D[nx][ny][0][0] > cur.f + c){
                        st.erase({D[nx][ny][0][0], {{nx, ny}, {0, 0}}});
                        D[nx][ny][0][0] = cur.f + c;
                        st.insert({D[nx][ny][0][0], {{nx, ny}, {0, 0}}});
                    }
                }
                if(D[x][y][j][1] > cur.f + b){
                    st.erase({D[x][y][j][1], {{x, y}, {j, 1}}});
                    D[x][y][j][1] = D[x][y][0][0] + b;
                    st.insert({D[x][y][j][1], {{x, y}, {j, 1}}});
                }
            }
        }
    }
    ll ans = D[x[n]][y[n]][0][0];
    for(int i = 0; i < 4; i++){
        ans = min(D[x[n]][y[n]][i][1], ans);
    }
    cout << ans;
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 8788 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 369 ms 27924 KB Output is correct
4 Correct 392 ms 29352 KB Output is correct
5 Correct 83 ms 8956 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 429 ms 31440 KB Output is correct
2 Correct 437 ms 32124 KB Output is correct
3 Correct 295 ms 24348 KB Output is correct
4 Correct 243 ms 26316 KB Output is correct
5 Correct 338 ms 26700 KB Output is correct
6 Correct 301 ms 30256 KB Output is correct
7 Correct 503 ms 33564 KB Output is correct
8 Correct 443 ms 33272 KB Output is correct
9 Correct 513 ms 33100 KB Output is correct
10 Correct 74 ms 9420 KB Output is correct
11 Correct 488 ms 33368 KB Output is correct
12 Correct 454 ms 32752 KB Output is correct
13 Correct 253 ms 25164 KB Output is correct
14 Correct 415 ms 33456 KB Output is correct
15 Correct 337 ms 29132 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 8788 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 369 ms 27924 KB Output is correct
4 Correct 392 ms 29352 KB Output is correct
5 Correct 83 ms 8956 KB Output is correct
6 Correct 429 ms 31440 KB Output is correct
7 Correct 437 ms 32124 KB Output is correct
8 Correct 295 ms 24348 KB Output is correct
9 Correct 243 ms 26316 KB Output is correct
10 Correct 338 ms 26700 KB Output is correct
11 Correct 301 ms 30256 KB Output is correct
12 Correct 503 ms 33564 KB Output is correct
13 Correct 443 ms 33272 KB Output is correct
14 Correct 513 ms 33100 KB Output is correct
15 Correct 74 ms 9420 KB Output is correct
16 Correct 488 ms 33368 KB Output is correct
17 Correct 454 ms 32752 KB Output is correct
18 Correct 253 ms 25164 KB Output is correct
19 Correct 415 ms 33456 KB Output is correct
20 Correct 337 ms 29132 KB Output is correct
21 Correct 95 ms 9272 KB Output is correct
22 Correct 620 ms 26296 KB Output is correct
23 Correct 560 ms 23112 KB Output is correct
24 Correct 645 ms 23884 KB Output is correct
25 Correct 510 ms 30068 KB Output is correct
26 Correct 587 ms 26488 KB Output is correct
27 Correct 355 ms 20040 KB Output is correct
28 Correct 324 ms 20684 KB Output is correct
29 Correct 502 ms 24268 KB Output is correct
30 Correct 250 ms 20416 KB Output is correct
31 Correct 566 ms 33372 KB Output is correct
32 Correct 651 ms 32196 KB Output is correct
33 Correct 331 ms 30120 KB Output is correct
34 Correct 629 ms 29684 KB Output is correct
35 Correct 259 ms 20300 KB Output is correct