oj.uz

Submission #527892

# Submission time Handle Problem Language Result Execution time Memory
527892 2022-02-18T16:27:27 Z AdamGS Soccer (JOI17_soccer) C++17
100 / 100
 767 ms 39192 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
const int LIM=507, MAXN=1e5+7;
const ll INF=1e18+7;
int dx[]={1, 0, -1, 0}, dy[]={0, 1, 0, -1};
ll wart[LIM][LIM], odl[LIM][LIM][5], h, w, a, b, c, n;
pair<int,int>T[MAXN];
bool ok(int a, int b) {
    return 0<=a && a<h && 0<=b && b<w;
}
void BFS() {
    rep(i, h) rep(j, w) wart[i][j]=INF;
    queue<pair<int,int>>q;
    rep(i, n) {
        wart[T[i].st][T[i].nd]=0;
        q.push({T[i].st, T[i].nd});
    }
    while(!q.empty()) {
        int x=q.front().st, y=q.front().nd; q.pop();
        rep(i, 4) if(ok(x+dx[i], y+dy[i]) && wart[x+dx[i]][y+dy[i]]==INF) {
            wart[x+dx[i]][y+dy[i]]=wart[x][y]+c;
            q.push({x+dx[i], y+dy[i]});
        }
    }
}
void dijkstra() {
    rep(i, h) rep(j, w) rep(l, 5) odl[i][j][l]=INF;
    priority_queue<pair<ll,pair<pair<int,int>,int>>>q;
    q.push({0, {{T[0].st, T[0].nd}, 0}});
    while(!q.empty()) {
        ll o=-q.top().st, x=q.top().nd.st.st, y=q.top().nd.st.nd, l=q.top().nd.nd; q.pop();
        if(odl[x][y][l]<=o) continue;
        odl[x][y][l]=o;
        if(!l) {
            rep(i, 4) if(ok(x+dx[i], y+dy[i])) {
                if(odl[x+dx[i]][y+dy[i]][0]>o+c) q.push({-o-c, {{x+dx[i], y+dy[i]}, 0}});
                if(odl[x+dx[i]][y+dy[i]][i+1]>o+a+b) q.push({-o-a-b, {{x+dx[i], y+dy[i]}, i+1}});
            }
            continue;
        }
        if(odl[x][y][0]>o+wart[x][y]) q.push({-o-wart[x][y], {{x, y}, 0}});
        if(ok(x+dx[l-1], y+dy[l-1]) && odl[x+dx[l-1]][y+dy[l-1]][l]>o+a) 
            q.push({-o-a, {{x+dx[l-1], y+dy[l-1]}, l}});
    }
}
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> h >> w >> a >> b >> c >> n; ++h; ++w;
    rep(i, n) cin >> T[i].st >> T[i].nd;
    BFS();
    dijkstra();
    ll ans=INF;
    rep(i, 5) ans=min(ans, odl[T[n-1].st][T[n-1].nd][i]);
    cout << ans << '\n';
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 8288 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 440 ms 18552 KB Output is correct
4 Correct 514 ms 24720 KB Output is correct
5 Correct 127 ms 6916 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 733 ms 37064 KB Output is correct
2 Correct 746 ms 37024 KB Output is correct
3 Correct 450 ms 22320 KB Output is correct
4 Correct 467 ms 18612 KB Output is correct
5 Correct 504 ms 24604 KB Output is correct
6 Correct 479 ms 24720 KB Output is correct
7 Correct 722 ms 37076 KB Output is correct
8 Correct 553 ms 37004 KB Output is correct
9 Correct 755 ms 37096 KB Output is correct
10 Correct 93 ms 9168 KB Output is correct
11 Correct 724 ms 37144 KB Output is correct
12 Correct 717 ms 37048 KB Output is correct
13 Correct 377 ms 22268 KB Output is correct
14 Correct 731 ms 37120 KB Output is correct
15 Correct 572 ms 37016 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 8288 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 440 ms 18552 KB Output is correct
4 Correct 514 ms 24720 KB Output is correct
5 Correct 127 ms 6916 KB Output is correct
6 Correct 733 ms 37064 KB Output is correct
7 Correct 746 ms 37024 KB Output is correct
8 Correct 450 ms 22320 KB Output is correct
9 Correct 467 ms 18612 KB Output is correct
10 Correct 504 ms 24604 KB Output is correct
11 Correct 479 ms 24720 KB Output is correct
12 Correct 722 ms 37076 KB Output is correct
13 Correct 553 ms 37004 KB Output is correct
14 Correct 755 ms 37096 KB Output is correct
15 Correct 93 ms 9168 KB Output is correct
16 Correct 724 ms 37144 KB Output is correct
17 Correct 717 ms 37048 KB Output is correct
18 Correct 377 ms 22268 KB Output is correct
19 Correct 731 ms 37120 KB Output is correct
20 Correct 572 ms 37016 KB Output is correct
21 Correct 152 ms 7868 KB Output is correct
22 Correct 670 ms 24764 KB Output is correct
23 Correct 667 ms 23472 KB Output is correct
24 Correct 760 ms 24932 KB Output is correct
25 Correct 506 ms 24692 KB Output is correct
26 Correct 552 ms 18800 KB Output is correct
27 Correct 329 ms 13936 KB Output is correct
28 Correct 451 ms 14944 KB Output is correct
29 Correct 533 ms 20336 KB Output is correct
30 Correct 548 ms 16008 KB Output is correct
31 Correct 680 ms 37008 KB Output is correct
32 Correct 742 ms 39192 KB Output is correct
33 Correct 429 ms 24740 KB Output is correct
34 Correct 767 ms 37076 KB Output is correct
35 Correct 349 ms 14644 KB Output is correct