oj.uz

Submission #738402

# Submission time Handle Problem Language Result Execution time Memory
738402 2023-05-08T16:25:54 Z 1075508020060209tc Soccer (JOI17_soccer) C++14
100 / 100
 941 ms 57660 KB 
#include<bits/stdc++.h>

using namespace std;
#define int long long
int H;int W;
int n;
int A;int B;int C;
int dir[5]={0,1,0,-1,0};
pair<int,int>ar[500005];
int mht[510][510];
int ok(int x,int y){
if(x>=1&&x<=H&&y>=1&&y<=W){return 1;}
return 0;
}
void mhtcalc(){
for(int i=1;i<=H;i++){
    for(int j=1;j<=W;j++){
        mht[i][j]=-1;
    }
}
queue<pair<int,int>>q;
for(int i=1;i<=n;i++){
    mht[ar[i].first][ar[i].second]=0;
    q.push(ar[i]);
}
while(q.size()){
    int nwx=q.front().first;
    int nwy=q.front().second;
    q.pop();
    for(int i=0;i<4;i++){
        int x=nwx+dir[i];int y=nwy+dir[i+1];
        if(!ok(x,y)){continue;}
        if(mht[x][y]==-1){
            mht[x][y]=mht[nwx][nwy]+1;
            q.push({x,y});
        }
    }
}
}
int dis[5][510][510];
int vis[5][510][510];


signed main(){
cin>>H>>W;
cin>>A>>B>>C;
cin>>n;
H++;W++;
for(int i=1;i<=n;i++){
    cin>>ar[i].first>>ar[i].second;
    ar[i].first++;
    ar[i].second++;
}
mhtcalc();

for(int i=0;i<=4;i++){
    for(int a=1;a<=H;a++){
        for(int b=1;b<=W;b++){
            dis[i][a][b]=1e18;
        }
    }
}
priority_queue<pair<int,array<int,3>>,vector<pair<int,array<int,3>>>,greater<pair<int,array<int,3>>>>pq;
dis[0][ar[1].first][ar[1].second]=0;
pq.push({0,{0,ar[1].first,ar[1].second}});

while(pq.size()){
    int nwd=pq.top().second[0];
    int nwx=pq.top().second[1];
    int nwy=pq.top().second[2];
    pq.pop();
    if(vis[nwd][nwx][nwy]){continue;}
    vis[nwd][nwx][nwy]=1;
    if(nwd==0){
        for(int i=0;i<4;i++){
            int x=nwx+dir[i];int y=nwy+dir[i+1];
            if(!ok(x,y)){continue;}
            if(vis[0][x][y]){continue;}
            dis[0][x][y]=min(dis[0][x][y],dis[0][nwx][nwy]+C);
            pq.push({dis[0][x][y],{0,x,y}});
        }
        for(int i=1;i<=4;i++){
            int x=nwx+dir[i-1];int y=nwy+dir[i];
            if(!ok(x,y)){continue;}
            if(vis[i][x][y]){continue;}
            dis[i][x][y]=min(dis[i][x][y],dis[0][nwx][nwy]+A+B);
            pq.push({dis[i][x][y],{i,x,y}});
        }
        continue;
    }
    dis[0][nwx][nwy]=min(dis[0][nwx][nwy],dis[nwd][nwx][nwy]+mht[nwx][nwy]*C);
    pq.push({dis[0][nwx][nwy],{0,nwx,nwy}});
    int x=nwx+dir[nwd-1];int y=nwy+dir[nwd];
    if(ok(x,y)&&!vis[nwd][x][y]){
        dis[nwd][x][y]=min(dis[nwd][x][y],dis[nwd][nwx][nwy]+A);
        pq.push({dis[nwd][x][y],{nwd,x,y}});
    }
}
int ans=dis[0][ar[n].first][ar[n].second];
for(int i=1;i<=4;i++){
    ans=min(ans,dis[i][ar[n].first][ar[n].second]);
}
cout<<ans<<endl;

}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 16160 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 590 ms 28876 KB Output is correct
4 Correct 632 ms 35196 KB Output is correct
5 Correct 193 ms 15976 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 804 ms 54004 KB Output is correct
2 Correct 799 ms 53916 KB Output is correct
3 Correct 582 ms 33140 KB Output is correct
4 Correct 627 ms 26952 KB Output is correct
5 Correct 562 ms 36808 KB Output is correct
6 Correct 635 ms 36092 KB Output is correct
7 Correct 818 ms 54852 KB Output is correct
8 Correct 684 ms 55028 KB Output is correct
9 Correct 883 ms 54632 KB Output is correct
10 Correct 119 ms 25900 KB Output is correct
11 Correct 802 ms 54416 KB Output is correct
12 Correct 815 ms 54036 KB Output is correct
13 Correct 513 ms 33008 KB Output is correct
14 Correct 798 ms 54552 KB Output is correct
15 Correct 623 ms 54936 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 16160 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 590 ms 28876 KB Output is correct
4 Correct 632 ms 35196 KB Output is correct
5 Correct 193 ms 15976 KB Output is correct
6 Correct 804 ms 54004 KB Output is correct
7 Correct 799 ms 53916 KB Output is correct
8 Correct 582 ms 33140 KB Output is correct
9 Correct 627 ms 26952 KB Output is correct
10 Correct 562 ms 36808 KB Output is correct
11 Correct 635 ms 36092 KB Output is correct
12 Correct 818 ms 54852 KB Output is correct
13 Correct 684 ms 55028 KB Output is correct
14 Correct 883 ms 54632 KB Output is correct
15 Correct 119 ms 25900 KB Output is correct
16 Correct 802 ms 54416 KB Output is correct
17 Correct 815 ms 54036 KB Output is correct
18 Correct 513 ms 33008 KB Output is correct
19 Correct 798 ms 54552 KB Output is correct
20 Correct 623 ms 54936 KB Output is correct
21 Correct 223 ms 14612 KB Output is correct
22 Correct 837 ms 38880 KB Output is correct
23 Correct 842 ms 35584 KB Output is correct
24 Correct 900 ms 38824 KB Output is correct
25 Correct 670 ms 37240 KB Output is correct
26 Correct 767 ms 29212 KB Output is correct
27 Correct 559 ms 25288 KB Output is correct
28 Correct 642 ms 26012 KB Output is correct
29 Correct 724 ms 28756 KB Output is correct
30 Correct 583 ms 26168 KB Output is correct
31 Correct 804 ms 54620 KB Output is correct
32 Correct 941 ms 57660 KB Output is correct
33 Correct 506 ms 36220 KB Output is correct
34 Correct 883 ms 55428 KB Output is correct
35 Correct 564 ms 26396 KB Output is correct