Submission #361254

#	Time	Username	Problem	Language	Result	Execution time	Memory
361254		jainbot27	Soccer (JOI17_soccer)	C++17	30 / 100	3033 ms	69288 KiB

soccer

#include <bits/stdc++.h>
using namespace std;

#define f first
#define s second
#define pb push_back
#define ar array
#define all(x) x.begin(), x.end()
#define siz(x) (int)x.size()

#define FOR(x, y, z) for(int x = (y); x < (z); x++)
#define ROF(x, z, y) for(int x = (y-1); x >= (z); x--)
#define F0R(x, z) FOR(x, 0, z)
#define R0F(x, z) ROF(x, 0, z)
#define trav(x, y) for(auto&x:y)

using ll = long long;
using vi = vector<int>;
using vl = vector<long long>;
using pii = pair<int, int>;
using vpii = vector<pair<int, int>>;

template<class T> inline bool ckmin(T&a, T b) {return b < a ? a = b, 1 : 0;}
template<class T> inline bool ckmax(T&a, T b) {return b > a ? a = b, 1 : 0;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const char nl = '\n';
const int mxK = 100001;
const int mxN = 501;
const int MOD = 1e9 + 7;
const long long infLL = 1e18;

using node = pair<ll, ar<int, 2>>;
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};


ll A, B, C;
int n, m;
int k;
pii pts[mxK];
bool dude[mxN][mxN];
ll dist[mxN][mxN];
int near[mxN][mxN];

queue<pii> bfs;
priority_queue<node, vector<node>, greater<node>> pq;

int32_t main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    memset(near, 0x3f, sizeof(near));
    cin >> n >> m >> A >> B >> C >> k;
    n++; m++;
    F0R(i, k){
        cin >> pts[i].f >> pts[i].s;
        near[pts[i].f][pts[i].s] = 0;
        bfs.push({pts[i].f, pts[i].s});
    }
    while(!bfs.empty()){
        pii x = bfs.front();
        bfs.pop();
        F0R(i, 4){
            pii nx = x;
            nx.f += dx[i];
            nx.s += dy[i];
            if(nx.f < 0 || nx.f >= n || nx.s < 0 || nx.s >= m) continue;
            if(ckmin(near[nx.f][nx.s], near[x.f][x.s]+1)){
                bfs.push(nx);
            }
        } 
    }
    F0R(i, n){
        F0R(j, m){
            dist[i][j] = infLL;
        }
    }
    dist[pts[0].f][pts[0].s] = 0;
    pq.push({0, {pts[0].f, pts[0].s}});

    while(!pq.empty()){
        node U = pq.top();
        ll du = U.f;
        ar<int, 2> u = U.s;
        pq.pop();
        if(du!=dist[u[0]][u[1]]){
            continue;
        }
        F0R(i, n){
            if(ckmin(dist[i][u[1]], dist[u[0]][u[1]]+C*abs(u[0]-i))){
                pq.push({dist[i][u[1]], {i, u[1]}});
            }
            if(ckmin(dist[i][u[1]], dist[u[0]][u[1]]+B+A*abs(u[0]-i)+C*near[i][u[1]])){
                pq.push({dist[i][u[1]], {i, u[1]}});
            }
        }
        F0R(j, m){
            if(ckmin(dist[u[0]][j], du+C*abs(u[1]-j))){
                pq.push({dist[u[0]][j], {u[0], j}});
            }
            if(ckmin(dist[u[0]][j], du+B+A*abs(u[1]-j)+C*(near[u[0]][j]))){
                pq.push({dist[u[0]][j], {u[0], j}});
            }
        }
    } 
    //F0R(i, n){
    //    F0R(j, m){
    //        cout << near[i][j] << ' ';
    //    }
    //    cout << nl;
    //}
    //F0R(i, n){
    //    F0R(j, m){
    //        cout << dist[i][j] << ' ';
    //    }
    //    cout << nl;
    //}
    cout << dist[pts[k-1].f][pts[k-1].s] << nl;

    return 0;
}

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