Submission #46754

#	Time	Username	Problem	Language	Result	Execution time	Memory
46754		nickyrio	Soccer (JOI17_soccer)	C++17	35 / 100	1170 ms	262144 KiB

soccer

//https://oj.uz/problem/view/JOI17_soccer
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)
#define REP(i, a) for (int i = 0; i < (a); ++i)
#define DEBUG(x) { cerr << #x << '=' << x << endl; }
#define Arr(a, l, r) { cerr << #a << " = {"; FOR(_, l, r) cerr << ' ' << a[_]; cerr << "}\n"; }
#define N 505
#define pp pair<int, int>
#define endl '\n'
#define IO ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define taskname ""
#define bit(S, i) (((S) >> (i)) & 1)
using namespace std;
 
 
struct Data{
    int u, v;
    long long dist;
    Data() {}
    Data(int u, int v, long long dist):u(u), v(v), dist(dist) {}
};
 
struct cmp{
    bool operator() (Data a, Data b) {
        return a.dist > b.dist;
    }
};
const int dd[4] = {1, 0, -1, 0};
const int cc[4] = {0, 1, 0, -1};
 
int h, w, a, b, c, n, s[N * N], t[N * N];
long long dis[N][N], f[N][N];
 
bool inside(int i, int j) {
    return i >= 0 && j >= 0 && j <= w && i <= h;
}
 
int main() {
    #ifdef NERO
    freopen("test.inp","r",stdin);
    freopen("test.out","w",stdout);
    double stime = clock();
    #else 
        //freopen(taskname".inp","r",stdin);
        //freopen(taskname".out","w",stdout);
    #endif //NERO
    IO;
    cin >> h >> w >> a >> b >> c >> n;
    queue<pp> q;
    memset(dis, -1, sizeof dis);
    FOR(i, 1, n) {
        cin >> s[i] >> t[i];
        dis[s[i]][t[i]] = 0;
        q.push(pp(s[i], t[i]));
    }
    while (!q.empty()) {
        pp u = q.front(); q.pop();
        REP(i, 4) {
            pp v = pp(u.first + dd[i], u.second + cc[i]);
            if (inside(v.first, v.second) && dis[v.first][v.second] == -1) {
                dis[v.first][v.second] = dis[u.first][u.second] + c;
                q.push(v);
            }
        }
    }
    memset(f, 60, sizeof f);
    f[s[1]][t[1]] = 0;
    priority_queue<Data, vector<Data>, cmp> heap;
    heap.push(Data(s[1], t[1], 0));
    while (!heap.empty()) {
        Data u = heap.top(); heap.pop();
        if (u.dist != f[u.u][u.v]) continue;
        if (u.u == s[n] && u.v == t[n]) {
            cout << u.dist << '\n';
            return 0;
        }
        REP(i, 4) {
            // Kick the ball
            Data v = u;
            v.dist += b;
            while (inside(v.u + dd[i], v.v + cc[i])) {
                v.u += dd[i], v.v += cc[i];
                v.dist += a;
              //  cout << 'v' << v.u << ' ' << v.v << ' ' << v.dist +  dis[v.u][v.v] << '\n';
              //  cout << f[v.u][v.v] << '\n';
                if (f[v.u][v.v] > v.dist + dis[v.u][v.v]) {
                    f[v.u][v.v] = v.dist + dis[v.u][v.v];
                    Data newV = v;
                    newV.dist += dis[v.u][v.v];
                    heap.push(newV);
                } 
            }
            // Move
            v.u = u.u + dd[i];
            v.v = u.v + cc[i];
            v.dist = u.dist + c;
            if (inside(v.u, v.v) && f[v.u][v.v] > v.dist) {
                f[v.u][v.v] = v.dist;
                heap.push(v);
            }
        }
    } 
    #ifdef NERO
    double etime = clock();
    cerr << "Execution time: " << (etime - stime) / CLOCKS_PER_SEC * 1000 << " ms.\n";
    #endif // NERO
}

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