Submission #1013296

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013296		snpmrnhlol	Soccer (JOI17_soccer)	C++17	100 / 100	196 ms	19340 KiB

soccer

#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 / 5
• Subtask 2: 30 / 30
• Subtask 3: 65 / 65