oj.uz

Submission #758358

# Submission time Handle Problem Language Result Execution time Memory
758358 2023-06-14T13:48:37 Z 1bin Soccer (JOI17_soccer) C++14
100 / 100
 770 ms 49780 KB 
#include <bits/stdc++.h>

using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 505;
ll h, w, a, b, c, n, x, y, P[NMAX][NMAX], dist[5][NMAX][NMAX];
vector<pair<ll, ll>> v;
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};

int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> h >> w >> a >> b >> c >> n;
    queue<pair<int, int>> q;
    memset(P, -1, sizeof(P));
    for(int i = 0; i < n; i++) {
        cin >> y >> x;
        q.emplace(x, y); P[x][y] = 0;
        v.emplace_back(x, y);
    }
    while(q.size()){
        auto&[x, y] = q.front(); q.pop();
        for(int k = 0; k < 4; k++){
            int ny = y + dy[k];
            int nx = x + dx[k];
            if(ny < 0 || nx < 0 || ny > h || nx > w || P[nx][ny] != -1) continue;
            P[nx][ny] = P[x][y] + c;
            q.emplace(nx, ny);
        }
    }
    
    memset(dist, 0x3f, sizeof(dist));
    priority_queue<tuple<ll, ll, ll, ll>> pq;
    pq.emplace(0, 4, v[0].first, v[0].second);
    dist[4][v[0].first][v[0].second] = 0;
    
    while(pq.size()){
        auto[d, t, x, y] = pq.top(); pq.pop();
        d = -d;
        if(d > dist[t][x][y]) continue;
        
        if(t < 4){
            if(d < dist[4][x][y]){
                dist[4][x][y] = d;
                pq.emplace(-d, 4, x, y);    
            }
            int ny = y + dy[t];
            int nx = x + dx[t];
            if(ny < 0 || nx < 0 || ny > h || nx > w) continue;
            if(d + a < dist[t][nx][ny]){
                dist[t][nx][ny] = d + a;
                pq.emplace(-d-a, t, nx, ny);
            }
        }
        else{
            for(int k = 0; k < 4; k++){
               int ny = y + dy[k];
                int nx = x + dx[k];
                if(ny < 0 || nx < 0 || ny > h || nx > w) continue;
                if(d + c < dist[4][nx][ny]){
                    dist[4][nx][ny] = d + c;
                    pq.emplace(-d-c, 4, nx, ny);
                }
                if(d + a + b + P[x][y] < dist[k][nx][ny]){
                    dist[k][nx][ny] = d + a + b + P[x][y];
                    pq.emplace(-d-a-b-P[x][y], k, nx, ny);
                }
            }
        }   
    }
    cout << dist[4][v[n - 1].first][v[n - 1].second];
    return 0;
}

Compilation message

soccer.cpp: In function 'int main()':
soccer.cpp:25:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   25 |         auto&[x, y] = q.front(); q.pop();
      |              ^
soccer.cpp:41:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   41 |         auto[d, t, x, y] = pq.top(); pq.pop();
      |             ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 20628 KB Output is correct
2 Correct 7 ms 12244 KB Output is correct
3 Correct 529 ms 45172 KB Output is correct
4 Correct 531 ms 45328 KB Output is correct
5 Correct 146 ms 20556 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 645 ms 45184 KB Output is correct
2 Correct 564 ms 45224 KB Output is correct
3 Correct 384 ms 45264 KB Output is correct
4 Correct 389 ms 28880 KB Output is correct
5 Correct 425 ms 45244 KB Output is correct
6 Correct 390 ms 45224 KB Output is correct
7 Correct 525 ms 45344 KB Output is correct
8 Correct 475 ms 45248 KB Output is correct
9 Correct 572 ms 45468 KB Output is correct
10 Correct 72 ms 20672 KB Output is correct
11 Correct 548 ms 45280 KB Output is correct
12 Correct 558 ms 45192 KB Output is correct
13 Correct 308 ms 45208 KB Output is correct
14 Correct 552 ms 45300 KB Output is correct
15 Correct 426 ms 45240 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 20628 KB Output is correct
2 Correct 7 ms 12244 KB Output is correct
3 Correct 529 ms 45172 KB Output is correct
4 Correct 531 ms 45328 KB Output is correct
5 Correct 146 ms 20556 KB Output is correct
6 Correct 645 ms 45184 KB Output is correct
7 Correct 564 ms 45224 KB Output is correct
8 Correct 384 ms 45264 KB Output is correct
9 Correct 389 ms 28880 KB Output is correct
10 Correct 425 ms 45244 KB Output is correct
11 Correct 390 ms 45224 KB Output is correct
12 Correct 525 ms 45344 KB Output is correct
13 Correct 475 ms 45248 KB Output is correct
14 Correct 572 ms 45468 KB Output is correct
15 Correct 72 ms 20672 KB Output is correct
16 Correct 548 ms 45280 KB Output is correct
17 Correct 558 ms 45192 KB Output is correct
18 Correct 308 ms 45208 KB Output is correct
19 Correct 552 ms 45300 KB Output is correct
20 Correct 426 ms 45240 KB Output is correct
21 Correct 107 ms 16496 KB Output is correct
22 Correct 770 ms 28828 KB Output is correct
23 Correct 651 ms 28884 KB Output is correct
24 Correct 762 ms 29080 KB Output is correct
25 Correct 497 ms 45316 KB Output is correct
26 Correct 487 ms 29192 KB Output is correct
27 Correct 292 ms 14984 KB Output is correct
28 Correct 329 ms 15796 KB Output is correct
29 Correct 445 ms 33456 KB Output is correct
30 Correct 330 ms 21120 KB Output is correct
31 Correct 558 ms 45408 KB Output is correct
32 Correct 695 ms 49780 KB Output is correct
33 Correct 382 ms 45208 KB Output is correct
34 Correct 728 ms 45392 KB Output is correct
35 Correct 362 ms 16700 KB Output is correct