Submission #46753

#	Time	Username	Problem	Language	Result	Execution time	Memory
46753		nickyrio	Soccer (JOI17_soccer)	C++17	100 / 100	359 ms	21128 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, dir;
    long long dist;
    Data() {}
    Data(int u, int v, long long dist, int dir):u(u), v(v), dist(dist), dir(dir) {}
};

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};

long long h, w, a, b, c, n, s[N * N], t[N * N];
long long dis[N][N], f[N][N][5];

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;
    FOR(i, 0, h) FOR(j, 0, w) {
        dis[i][j] = -1;
        REP(k, 5) f[i][j][k] = 1e18;
    }
    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] + 1;
                q.push(v);
            }
        }
    }
    f[s[1]][t[1]][4] = 0;
    priority_queue<Data, vector<Data>, cmp> heap;
    heap.push(Data(s[1], t[1], 0, 4));
    while (!heap.empty()) {
        Data u = heap.top(); heap.pop();
        if (u.dist > f[u.u][u.v][u.dir]) continue;
        if (u.dir == 4) {
            if (u.u == s[n] && u.v == t[n]) {
                cout << u.dist << '\n';
                return 0;
            }
            REP(i, 4) {
                // Start kicking ball
                Data v = Data(u.u + dd[i], u.v + cc[i], u.dist + a + b, i);
                if (inside(v.u, v.v) && f[v.u][v.v][v.dir] > v.dist) {
                    f[v.u][v.v][v.dir] = v.dist;
                    heap.push(v);
                }
                // Move
                v.dist = u.dist + c;
                v.dir = 4;
                if (inside(v.u, v.v) && f[v.u][v.v][v.dir] > v.dist) {
                    f[v.u][v.v][v.dir] = v.dist;      
                    heap.push(v);
                }
            }

        }
        else { // Ball is moving
            // Keep moving
            Data v = u;
            v.u += dd[v.dir],v.v += cc[v.dir];
            v.dist += a;
            if (inside(v.u, v.v) && f[v.u][v.v][v.dir] > v.dist) {
                f[v.u][v.v][v.dir] = v.dist;
                heap.push(v);
            }
            //Stop and another player move ball
            v = u;
            v.dir = 4;
            v.dist = u.dist + dis[v.u][v.v] * c;
            if (inside(v.u, v.v) && f[v.u][v.v][v.dir] > v.dist) {
                f[v.u][v.v][v.dir] = v.dist;
                heap.push(v);
            }
        }
    }
    #ifdef NERO
    double etime = clock();
    cerr << "Execution time: " << (etime - stime) / CLOCKS_PER_SEC * 1000 << " ms.\n";
    #endif // NERO
}

Compilation message (stderr)

soccer.cpp: In constructor 'Data::Data(int, int, long long int, int)':
soccer.cpp:19:15: warning: 'Data::dist' will be initialized after [-Wreorder]
     long long dist;
               ^~~~
soccer.cpp:18:15: warning:   'int Data::dir' [-Wreorder]
     int u, v, dir;
               ^~~
soccer.cpp:21:5: warning:   when initialized here [-Wreorder]
     Data(int u, int v, long long dist, int dir):u(u), v(v), dist(dist), dir(dir) {}
     ^~~~

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