oj.uz

Submission #143351

# Submission time Handle Problem Language Result Execution time Memory
143351 2019-08-13T18:11:07 Z osaaateiasavtnl Soccer (JOI17_soccer) C++14
100 / 100
 374 ms 24752 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
#define x first
#define y second
const int N = 507, INF = 1e18 + 7, MAXP = 1e5 + 7;
struct State {
    int x, y, k, c; bool t;
    bool const operator < (const State s) const { return c > s.c; }
};
vector <ii> v = { {0, -1}, {0, 1}, {-1, 0}, {1, 0} };
int n, m, A, B, C, P;
bool check(int i, int j) { return 0 <= i && 0 <= j && i <= n && j <= m; }
bool us[N][N]; int dist[N][N];
void bfs() {
    queue <ii> q;
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= m; ++j) {
            dist[i][j] = INF;
            if (us[i][j]) { dist[i][j] = 0; q.push({i, j}); }
        }
    }
    while (q.size()) {
        auto p = q.front(); q.pop();
        for (auto e : v) {
            if (check(p.x + e.x, p.y + e.y) && dist[p.x][p.y] + 1 < dist[p.x + e.x][p.y + e.y]) {
                dist[p.x + e.x][p.y + e.y] = dist[p.x][p.y] + 1;
                q.push({p.x + e.x, p.y + e.y});
            }
        }
    }
}
priority_queue <State> mq;
ii f[MAXP];
int dp1[N][N][4], dp2[N][N];
void upd(int x, int y, int k, int c) {
    if (check(x, y) && c < dp1[x][y][k]) {
        dp1[x][y][k] = c;
        mq.push({x, y, k, dp1[x][y][k], 0});
    }
}
void upd(int x, int y, int c) {
    if (check(x, y) && c < dp2[x][y]) {
        dp2[x][y] = c;
        mq.push({x, y, -1, dp2[x][y], 1});
    }
}
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    cin >> n >> m >> A >> B >> C >> P;  
    for (int i = 0; i < P; ++i) { int x, y; cin >> x >> y; us[x][y] = 1; f[i] = {x, y}; }
    bfs();
    for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) for (int k = 0; k < 4; ++k) dp1[i][j][k] = INF;
    for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) dp2[i][j] = INF;
    upd(f[0].x, f[0].y, 0);
    while (mq.size()) {
        auto s = mq.top(); mq.pop();
        if (s.x == f[P - 1].x && s.y == f[P - 1].y) { cout << s.c << '\n'; exit(0); }
        if (s.t) {
            for (auto e : v) upd(s.x + e.x, s.y + e.y, s.c + C);
            for (int i = 0; i < 4; ++i) upd(s.x, s.y, i, s.c + B);
        }
        else {
            upd(s.x, s.y, s.c + C * dist[s.x][s.y]);
            upd(s.x + v[s.k].x, s.y + v[s.k].y, s.k, s.c + A);   
        }
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 14444 KB Output is correct
2 Correct 10 ms 10488 KB Output is correct
3 Correct 98 ms 22844 KB Output is correct
4 Correct 48 ms 17636 KB Output is correct
5 Correct 51 ms 12024 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 17844 KB Output is correct
2 Correct 36 ms 15312 KB Output is correct
3 Correct 126 ms 22616 KB Output is correct
4 Correct 301 ms 23004 KB Output is correct
5 Correct 142 ms 23000 KB Output is correct
6 Correct 187 ms 23124 KB Output is correct
7 Correct 118 ms 23068 KB Output is correct
8 Correct 118 ms 23092 KB Output is correct
9 Correct 28 ms 14128 KB Output is correct
10 Correct 28 ms 15340 KB Output is correct
11 Correct 209 ms 23108 KB Output is correct
12 Correct 205 ms 23004 KB Output is correct
13 Correct 144 ms 22616 KB Output is correct
14 Correct 97 ms 23100 KB Output is correct
15 Correct 27 ms 14228 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 14444 KB Output is correct
2 Correct 10 ms 10488 KB Output is correct
3 Correct 98 ms 22844 KB Output is correct
4 Correct 48 ms 17636 KB Output is correct
5 Correct 51 ms 12024 KB Output is correct
6 Correct 51 ms 17844 KB Output is correct
7 Correct 36 ms 15312 KB Output is correct
8 Correct 126 ms 22616 KB Output is correct
9 Correct 301 ms 23004 KB Output is correct
10 Correct 142 ms 23000 KB Output is correct
11 Correct 187 ms 23124 KB Output is correct
12 Correct 118 ms 23068 KB Output is correct
13 Correct 118 ms 23092 KB Output is correct
14 Correct 28 ms 14128 KB Output is correct
15 Correct 28 ms 15340 KB Output is correct
16 Correct 209 ms 23108 KB Output is correct
17 Correct 205 ms 23004 KB Output is correct
18 Correct 144 ms 22616 KB Output is correct
19 Correct 97 ms 23100 KB Output is correct
20 Correct 27 ms 14228 KB Output is correct
21 Correct 39 ms 12468 KB Output is correct
22 Correct 304 ms 22972 KB Output is correct
23 Correct 365 ms 17748 KB Output is correct
24 Correct 248 ms 17888 KB Output is correct
25 Correct 294 ms 23140 KB Output is correct
26 Correct 306 ms 23280 KB Output is correct
27 Correct 168 ms 14004 KB Output is correct
28 Correct 251 ms 14552 KB Output is correct
29 Correct 374 ms 19564 KB Output is correct
30 Correct 136 ms 14336 KB Output is correct
31 Correct 77 ms 17968 KB Output is correct
32 Correct 174 ms 24752 KB Output is correct
33 Correct 219 ms 23008 KB Output is correct
34 Correct 46 ms 15392 KB Output is correct
35 Correct 184 ms 14560 KB Output is correct