oj.uz

Submission #1013296

# Submission time Handle Problem Language Result Execution time Memory
1013296 2024-07-03T11:41:49 Z snpmrnhlol Soccer (JOI17_soccer) C++17
100 / 100
 196 ms 19340 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 501;
const int K = 1e5;
const ll inf = 1e18;
struct point{
    int x,y;
};
ll dist[N][N][3];
int dist2[N][N];
bool vis[N][N];
point player[K];
priority_queue <array<ll,4>> pq;
queue <array<int,2>> q;
int d[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
int n,m,a,b,c;
int k;
bool inbound(int x,int y){
    return 0 <= x && x <= n && 0 <= y && y <= m;
}
void add(ll nr,int x,int y,int id){
    if(dist[x][y][id] > nr){
        dist[x][y][id] = nr;
        pq.push({-nr,x,y,id});
    }
}
void bfs(){
    for(int i = 0;i < k;i++){
        q.push({player[i].x,player[i].y});
        vis[player[i].x][player[i].y] = 1;
        dist2[player[i].x][player[i].y] = 0;
    }
    while(!q.empty()){
        int x = q.front()[0];
        int y = q.front()[1];
        q.pop();
        for(int l = 0;l < 4;l++){
            int nx = x + d[l][0];
            int ny = y + d[l][1];
            if(inbound(nx,ny) && !vis[nx][ny]){
                vis[nx][ny] = 1;
                dist2[nx][ny] = dist2[x][y] + 1;
                q.push({nx,ny});
            }
        }
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m;
    cin>>a>>b>>c;
    cin>>k;
    for(int i = 0;i < k;i++){
        cin>>player[i].x>>player[i].y;
    }
    for(int i = 0;i <= n;i++){
        for(int j = 0;j <= m;j++){
            for(int l = 0;l < 3;l++){
                dist[i][j][l] = inf;
            }
        }
    }
    bfs();
    pq.push({0,player[0].x,player[0].y,0});
    dist[player[0].x][player[0].y][0] = 0;
    ///0 - on player
    ///1 - thrown left/right
    ///2 - thrown up/down
    while(!pq.empty()){
        auto x = pq.top();
        x[0] = -x[0];
        pq.pop();
        if(x[0] != dist[x[1]][x[2]][x[3]]){
            continue;
        }
        if(x[3] == 0){
            ///throw ball
            add(x[0] + b,x[1],x[2],1);
            add(x[0] + b,x[1],x[2],2);
            ///directional movement
            for(int l = 0;l < 4;l++){
                int nx = x[1] + d[l][0];
                int ny = x[2] + d[l][1];
                if(inbound(nx,ny)){
                    add(x[0] + c,nx,ny,x[3]);
                }
            }
        }else if(x[3] == 1){
            ///catch
            add(x[0] + 1ll*dist2[x[1]][x[2]]*c,x[1],x[2],0);
            ///directional movement
            for(int l = 2;l < 4;l++){
                int nx = x[1] + d[l][0];
                int ny = x[2] + d[l][1];
                if(inbound(nx,ny)){
                    add(x[0] + a,nx,ny,x[3]);
                }
            }
        }else{
            ///catch
            add(x[0] + 1ll*dist2[x[1]][x[2]]*c,x[1],x[2],0);
            ///directional movement
            for(int l = 0;l < 2;l++){
                int nx = x[1] + d[l][0];
                int ny = x[2] + d[l][1];
                if(inbound(nx,ny)){
                    add(x[0] + a,nx,ny,x[3]);
                }
            }
        }
    }
    /*for(ll i = 0;i <= n;i++){
        for(ll j = 0;j <= m;j++){
            cout<<dist[i][j][0]<<' ';
        }
        cout<<'\n';
    }*/
    cout<<dist[player[k - 1].x][player[k - 1].y][0]<<'\n';
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 8664 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 134 ms 17452 KB Output is correct
4 Correct 138 ms 16848 KB Output is correct
5 Correct 33 ms 6488 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 16592 KB Output is correct
2 Correct 133 ms 17216 KB Output is correct
3 Correct 107 ms 16328 KB Output is correct
4 Correct 95 ms 17600 KB Output is correct
5 Correct 101 ms 17372 KB Output is correct
6 Correct 96 ms 18384 KB Output is correct
7 Correct 133 ms 17856 KB Output is correct
8 Correct 133 ms 17604 KB Output is correct
9 Correct 157 ms 17084 KB Output is correct
10 Correct 23 ms 9600 KB Output is correct
11 Correct 148 ms 17088 KB Output is correct
12 Correct 158 ms 18140 KB Output is correct
13 Correct 85 ms 17356 KB Output is correct
14 Correct 150 ms 17344 KB Output is correct
15 Correct 125 ms 17096 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 8664 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 134 ms 17452 KB Output is correct
4 Correct 138 ms 16848 KB Output is correct
5 Correct 33 ms 6488 KB Output is correct
6 Correct 157 ms 16592 KB Output is correct
7 Correct 133 ms 17216 KB Output is correct
8 Correct 107 ms 16328 KB Output is correct
9 Correct 95 ms 17600 KB Output is correct
10 Correct 101 ms 17372 KB Output is correct
11 Correct 96 ms 18384 KB Output is correct
12 Correct 133 ms 17856 KB Output is correct
13 Correct 133 ms 17604 KB Output is correct
14 Correct 157 ms 17084 KB Output is correct
15 Correct 23 ms 9600 KB Output is correct
16 Correct 148 ms 17088 KB Output is correct
17 Correct 158 ms 18140 KB Output is correct
18 Correct 85 ms 17356 KB Output is correct
19 Correct 150 ms 17344 KB Output is correct
20 Correct 125 ms 17096 KB Output is correct
21 Correct 35 ms 7000 KB Output is correct
22 Correct 196 ms 16836 KB Output is correct
23 Correct 181 ms 13772 KB Output is correct
24 Correct 185 ms 14340 KB Output is correct
25 Correct 170 ms 16660 KB Output is correct
26 Correct 182 ms 17404 KB Output is correct
27 Correct 135 ms 9304 KB Output is correct
28 Correct 122 ms 9308 KB Output is correct
29 Correct 181 ms 13644 KB Output is correct
30 Correct 107 ms 9052 KB Output is correct
31 Correct 151 ms 18552 KB Output is correct
32 Correct 176 ms 19340 KB Output is correct
33 Correct 151 ms 16580 KB Output is correct
34 Correct 180 ms 18360 KB Output is correct
35 Correct 95 ms 9216 KB Output is correct