Submission #1007605

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007605		dimashhh	Soccer (JOI17_soccer)	C++17	35 / 100	3082 ms	32672 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);
}
set<pair<ll,pair<int,int>>> st;
int fx,fy;
ll dist[N][N];
set<int> R[N],C[N];
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;
            dist[i][j] = 1e17;
        }
    }
    for(int i = 1;i <= f;i++) {
        int s,t;
        cin >> s >> t;
        s++;
        t++;
        if(i == 1){
            dist[s][t] = 0;
            st.insert({0,{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});
            }
        }
    }
    for(int i = 1;i <= n;i++){
        R[i].insert(-m);
        R[i].insert(m + m);
    }
    for(int i = 1;i <= m;i++){
        C[i].insert(-n);
        C[i].insert(n + n);
    }
    while(!st.empty()){
        auto [d,t] = (*st.begin());
        st.erase(st.begin());
        int x = t.first,y = t.second;
        int l,r;
        auto it = C[y].lower_bound(x);
        r = (x + (*it)) / 2 + 1;
        it--;
        l = (x +(*it)) / 2 - 1;
        for(int x1 = max(1,l);x1 <= min(n,r);x1++){
            ll dd = min(abs(x-x1)*1ll*c+dist[x][y],dist[x][y] + val[x1][y] + abs(x1 - x) * a + (x1 != x ? b : 0));
            if(dd < dist[x1][y]){
                st.erase({dist[x1][y],{x1,y}});
                dist[x1][y] = dd;
                st.insert({dist[x1][y],{x1,y}});
            }
        }
        it = R[x].lower_bound(y);
        r = (y + (*it)) / 2 + 1;
        it--;
        l = (y +(*it)) / 2 - 1;
        for(int y1 = max(1,l);y1 <= min(m,r);y1++){
            ll dd = min(abs(y-y1)*1ll*c+dist[x][y],dist[x][y]  + val[x][y1] + abs(y - y1) * a + (y1 != y ? b : 0));
            if(dd < dist[x][y1]){
                st.erase({dist[x][y1],{x,y1}});
                dist[x][y1] = dd;
                st.insert({dist[x][y1],{x,y1}});
            }
        }
        R[x].insert(y);
        C[y].insert(x);
    }
    cout << dist[fx][fy];
}
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: 0 / 65