Submission #1007695

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007695		dimashhh	Soccer (JOI17_soccer)	C++17	100 / 100	1272 ms	87492 KiB

soccer

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
const int  N = 5e2 + 2, MOD = (int)1e9 + 7;
const int dx[] = {1,0,-1,0},dy[] = {0,1,0,-1};
int n,m,d[N][N];
ll val[N][N];
ll a,b,c;
queue<pair<int,int>> q;
bool check(int x,int y){
    return (x >= 1 && x <= n && y >= 1 && y <= m);
}
int fx,fy;
ll dist[4][2][N][N];
const ll inf = 1e17;
set<array<ll,5>> st;
void test(){
    cin >> n >> m >> a >> b >> c;
    n++;
    m++;
    int f;cin >> f;
    for(int i = 1;i <= n;i++){ 
        for(int j = 1;j <= m;j++){
            d[i][j] = 1e9;
            for(int dir = 0;dir < 4;dir++)
            {
                dist[dir][0][i][j] = inf;
                dist[dir][1][i][j] = inf;
            }
        }
    }
    for(int i = 1;i <= f;i++) {
        int s,t;
        cin >> s >> t;
        s++;
        t++;
        if(i == 1){
            for(int dir = 0;dir < 4;dir++){
                dist[dir][1][s][t] = 0;
                st.insert({0,dir,1,s,t});
            }
        }
        d[s][t] = 0;
        q.push({s,t});
        fx = s;fy = t;
    }
    while(!q.empty()){
        auto [x,y] = q.front();q.pop();
        val[x][y] = d[x][y] * c;
        for(int i = 0;i < 4;i++){
            int x1 = x + dx[i],y1 = y + dy[i];
            if(check(x1,y1) && d[x1][y1] > d[x][y] + 1){
                d[x1][y1] = d[x][y] +1;
                q.push({x1,y1});
            }
        }
    }
    while(!st.empty())
    {
        auto [D,di,is,x,y] = (*st.begin());
        st.erase(st.begin());
        if(is){
            for(int dir = 0;dir < 4;dir++){
                ll du = D + c;
                int i = x + dx[dir],j = y + dy[dir];
                if(check(i,j) && dist[dir][1][i][j] > du){
                    st.erase({dist[dir][1][i][j],dir,1,i,j});
                    dist[dir][1][i][j] = du;
                    st.insert({du,dir,1,i,j});
                }
                du = D + a + b;
                i = x + dx[dir],j = y + dy[dir];
                if(check(i,j) && dist[dir][0][i][j] > du){
                    st.erase({dist[dir][0][i][j],dir,0,i,j});
                    dist[dir][0][i][j] = du;
                    st.insert({du,dir,0,i,j});
                }
            }
        }
        else{
            int i = x + dx[di],j = y + dy[di];
            ll du = D + a;
            if(check(i,j) && du < dist[di][0][i][j])
            {
                st.erase({dist[di][0][i][j],di,0,i,j});
                dist[di][0][i][j] = du;
                st.insert({dist[di][0][i][j],di,0,i,j});
            }
            du = D + val[x][y];
            if(du < dist[di][1][x][y]){
                st.erase({dist[di][1][x][y],di,1,x,y});
                dist[di][1][x][y] = du;
                st.insert({du,di,1,x,y});
            }
        }
    }
    
    ll res = inf;
    for(int i = 0;i < 4;i++)
    {
        res = min(res,dist[i][0][fx][fy]);
        res = min(res,dist[i][1][fx][fy]);
    }
    cout << res << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
    int t = 1;
    // cin >> t;
    while(t--){
        test();
    }
}

• Subtask 1: 5 / 5
• Subtask 2: 30 / 30
• Subtask 3: 65 / 65