oj.uz

Submission #46753

# Submission time Handle Problem Language Result Execution time Memory
46753 2018-04-22T19:04:06 Z nickyrio Soccer (JOI17_soccer) C++17
100 / 100
 359 ms 21128 KB 
//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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 6772 KB Output is correct
2 Correct 2 ms 6772 KB Output is correct
3 Correct 91 ms 18716 KB Output is correct
4 Correct 42 ms 18716 KB Output is correct
5 Correct 47 ms 18716 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 18716 KB Output is correct
2 Correct 33 ms 18716 KB Output is correct
3 Correct 112 ms 18716 KB Output is correct
4 Correct 277 ms 18716 KB Output is correct
5 Correct 153 ms 18716 KB Output is correct
6 Correct 173 ms 18716 KB Output is correct
7 Correct 111 ms 18820 KB Output is correct
8 Correct 129 ms 18820 KB Output is correct
9 Correct 30 ms 18820 KB Output is correct
10 Correct 20 ms 18820 KB Output is correct
11 Correct 220 ms 18920 KB Output is correct
12 Correct 221 ms 18920 KB Output is correct
13 Correct 137 ms 18920 KB Output is correct
14 Correct 99 ms 18964 KB Output is correct
15 Correct 23 ms 18964 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 6772 KB Output is correct
2 Correct 2 ms 6772 KB Output is correct
3 Correct 91 ms 18716 KB Output is correct
4 Correct 42 ms 18716 KB Output is correct
5 Correct 47 ms 18716 KB Output is correct
6 Correct 43 ms 18716 KB Output is correct
7 Correct 33 ms 18716 KB Output is correct
8 Correct 112 ms 18716 KB Output is correct
9 Correct 277 ms 18716 KB Output is correct
10 Correct 153 ms 18716 KB Output is correct
11 Correct 173 ms 18716 KB Output is correct
12 Correct 111 ms 18820 KB Output is correct
13 Correct 129 ms 18820 KB Output is correct
14 Correct 30 ms 18820 KB Output is correct
15 Correct 20 ms 18820 KB Output is correct
16 Correct 220 ms 18920 KB Output is correct
17 Correct 221 ms 18920 KB Output is correct
18 Correct 137 ms 18920 KB Output is correct
19 Correct 99 ms 18964 KB Output is correct
20 Correct 23 ms 18964 KB Output is correct
21 Correct 26 ms 18964 KB Output is correct
22 Correct 258 ms 18964 KB Output is correct
23 Correct 313 ms 18964 KB Output is correct
24 Correct 214 ms 18964 KB Output is correct
25 Correct 213 ms 18964 KB Output is correct
26 Correct 264 ms 19112 KB Output is correct
27 Correct 123 ms 19112 KB Output is correct
28 Correct 258 ms 19112 KB Output is correct
29 Correct 359 ms 19112 KB Output is correct
30 Correct 139 ms 19112 KB Output is correct
31 Correct 78 ms 19112 KB Output is correct
32 Correct 151 ms 21128 KB Output is correct
33 Correct 197 ms 21128 KB Output is correct
34 Correct 43 ms 21128 KB Output is correct
35 Correct 181 ms 21128 KB Output is correct