oj.uz

Submission #1015404

# Submission time Handle Problem Language Result Execution time Memory
1015404 2024-07-06T10:16:14 Z Baytoro Soccer (JOI17_soccer) C++17
100 / 100
 713 ms 65340 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fr first
#define sc second
#define int ll
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.ren
int dist[505][505][2][4];
int d[505][505];
vector<int> dx={1,-1,0,0},
            dy={0,0,1,-1};
int h,w;
bool check(int x, int y) {
    if(x<1) return 0;
    if(x>h) return 0;
    if(y<1) return 0;
    if(y>w) return 0;
    return 1;
}
void solve() {
    cin>>h>>w;h++,w++;
    int a,b,c;cin>>a>>b>>c;
    int n;cin>>n;
    vector<int> s(n),t(n);
    memset(dist,0x3f3f3f,sizeof dist);
    memset(d,0x3f3f3f,sizeof d);
    queue<pair<int,pair<int,int>>> pq;
    priority_queue<array<int,5>, vector<array<int,5>>, greater<array<int,5>>> dq;
    for(int i=0;i<n;i++) {
        cin>>s[i]>>t[i]; s[i]++,t[i]++;
        pq.push({0,{s[i],t[i]}});
        d[s[i]][t[i]]=0;
    }

    while(!pq.empty()) {
        int D=pq.front().fr,x=pq.front().sc.fr,y=pq.front().sc.sc;pq.pop();
        if(d[x][y]!=D) continue;
        for(int i=0;i<4;i++) {
            int X=x+dx[i],Y=y+dy[i];
            if(check(X,Y) && d[X][Y]>d[x][y]+1) {
                d[X][Y]=d[x][y]+1;
                pq.push({d[x][y]+1,{X,Y}});
            }
        }
    }
    for(int i=0;i<4;i++) {
        dq.push({0,i,1,s[0],t[0]});
        dist[s[0]][t[0]][1][i]=0;
    }
    /*for(int i=1;i<=h;i++) {
        for(int j=1;j<=w;j++) cout<<d[i][j]<<' ';
        cout<<endl;
    }*/
    while(!dq.empty()) {
        int D=dq.top()[0],dir=dq.top()[1],ball=dq.top()[2],x=dq.top()[3],y=dq.top()[4];

        dq.pop();

        if(dist[x][y][ball][dir]!=D) continue;
        //cout<<x<<' '<<y<<' '<<ball<<dir<<' '<<D<<endl;
        if(ball) {
            for(int i=0;i<4;i++) {
                int dd=D+c;
                if(check(x+dx[i],y+dy[i]) && dist[x+dx[i]][y+dy[i]][1][i]>dd) {
                    dist[x+dx[i]][y+dy[i]][1][i]=dd;
                    dq.push({dd,i,1,x+dx[i],y+dy[i]});
                }
                dd=D+a+b;
                if(check(x+dx[i],y+dy[i]) && dist[x+dx[i]][y+dy[i]][0][i]>dd) {
                    dist[x+dx[i]][y+dy[i]][0][i]=dd;
                    dq.push({dd,i,0,x+dx[i],y+dy[i]});
                }
            }
        }
        else {
            int X=x+dx[dir],Y=y+dy[dir];
            int dd=D+a;
            if(check(X,Y) && dist[X][Y][0][dir]>dd) {
                dist[X][Y][0][dir]=dd;
                dq.push({dd,dir,0,X,Y});
            }
            dd=D+d[x][y]*c;
            if(check(x,y) && dist[x][y][1][dir]>dd) {
                dist[x][y][1][dir]=dd;
                dq.push({dd,dir,1,x,y});
            }
        }
    }
    int ans=1e18;
    for(int i=0;i<4;i++) {
        ans=min(ans,dist[s[n-1]][t[n-1]][0][i]);
        ans=min(ans,dist[s[n-1]][t[n-1]][1][i]);
    }
    cout<<ans<<endl;



}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t=1;//cin>>t;
    while(t--){
        solve();
    }
}
//#endif

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 24256 KB Output is correct
2 Correct 4 ms 18404 KB Output is correct
3 Correct 482 ms 30536 KB Output is correct
4 Correct 536 ms 39340 KB Output is correct
5 Correct 115 ms 19008 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 680 ms 60452 KB Output is correct
2 Correct 696 ms 60360 KB Output is correct
3 Correct 459 ms 40396 KB Output is correct
4 Correct 467 ms 30792 KB Output is correct
5 Correct 482 ms 39372 KB Output is correct
6 Correct 485 ms 39732 KB Output is correct
7 Correct 619 ms 61892 KB Output is correct
8 Correct 547 ms 59844 KB Output is correct
9 Correct 673 ms 60360 KB Output is correct
10 Correct 94 ms 29796 KB Output is correct
11 Correct 617 ms 60096 KB Output is correct
12 Correct 680 ms 60016 KB Output is correct
13 Correct 377 ms 39352 KB Output is correct
14 Correct 617 ms 61636 KB Output is correct
15 Correct 497 ms 60036 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 24256 KB Output is correct
2 Correct 4 ms 18404 KB Output is correct
3 Correct 482 ms 30536 KB Output is correct
4 Correct 536 ms 39340 KB Output is correct
5 Correct 115 ms 19008 KB Output is correct
6 Correct 680 ms 60452 KB Output is correct
7 Correct 696 ms 60360 KB Output is correct
8 Correct 459 ms 40396 KB Output is correct
9 Correct 467 ms 30792 KB Output is correct
10 Correct 482 ms 39372 KB Output is correct
11 Correct 485 ms 39732 KB Output is correct
12 Correct 619 ms 61892 KB Output is correct
13 Correct 547 ms 59844 KB Output is correct
14 Correct 673 ms 60360 KB Output is correct
15 Correct 94 ms 29796 KB Output is correct
16 Correct 617 ms 60096 KB Output is correct
17 Correct 680 ms 60016 KB Output is correct
18 Correct 377 ms 39352 KB Output is correct
19 Correct 617 ms 61636 KB Output is correct
20 Correct 497 ms 60036 KB Output is correct
21 Correct 129 ms 20956 KB Output is correct
22 Correct 626 ms 39660 KB Output is correct
23 Correct 633 ms 39376 KB Output is correct
24 Correct 661 ms 39920 KB Output is correct
25 Correct 511 ms 39628 KB Output is correct
26 Correct 585 ms 30384 KB Output is correct
27 Correct 316 ms 23132 KB Output is correct
28 Correct 411 ms 24156 KB Output is correct
29 Correct 533 ms 33940 KB Output is correct
30 Correct 346 ms 23132 KB Output is correct
31 Correct 624 ms 61772 KB Output is correct
32 Correct 644 ms 65340 KB Output is correct
33 Correct 449 ms 40560 KB Output is correct
34 Correct 713 ms 61376 KB Output is correct
35 Correct 319 ms 23252 KB Output is correct