Submission #234018

#TimeUsernameProblemLanguageResultExecution timeMemory
234018dolphingarlicSoccer (JOI17_soccer)C++14
100 / 100
622 ms23920 KiB
#include <bits/stdc++.h> #define FOR(i, x, y) for (int i = x; i < y; i++) typedef long long ll;using namespace std;struct P {int x, y, d;ll f;};bool operator<(P A, P B) { return A.f > B.f; }int h, w;ll v[501][501], t[501][501], d[501][501][6];bool vis[501][501][6];int dx[6]{0, 0, 0, 0, 1, -1}, dy[6]{0, 0, 1, -1, 0, 0};bool ins(int x, int y) { return (~x && ~y && x <= h && y <= w); }int main() {ios_base::sync_with_stdio(0);cin.tie(0);int n;ll a, b, c;P dest;priority_queue<P> pq;cin >> h >> w >> a >> b >> c >> n;memset(v, 0x3f, sizeof(v));memset(t, 0x3f, sizeof(t));memset(d, 0x3f, sizeof(d));FOR(i, 0, n) {int x, y;cin >> x >> y;v[x][y] = 0;if (!i) pq.push({x, y, 1, 0}), d[x][y][1] = 0;if (i == n - 1) dest = {x, y, 0, 0};}FOR(i, 1, h + 1) FOR(j, 0, w + 1) {v[i][j] = min(v[i][j], v[i - 1][j] + 1);v[h - i][j] = min(v[h - i][j], v[h - i + 1][j] + 1);}FOR(i, 0, h + 1) FOR(j, 0, w + 1) FOR(k, 0, w + 1) {t[i][j] = min(t[i][j], v[i][k] + abs(j - k));}while (pq.size()) {P curr = pq.top();pq.pop();if (!vis[curr.x][curr.y][curr.d]) {vis[curr.x][curr.y][curr.d] = true;if (!curr.d) {if (curr.f + t[curr.x][curr.y] * c < d[curr.x][curr.y][1]) {d[curr.x][curr.y][1] = curr.f + t[curr.x][curr.y] * c;pq.push({curr.x, curr.y, 1, curr.f + t[curr.x][curr.y] * c});}} else if (curr.d == 1) {FOR(i, 2, 6) {int nx = curr.x + dx[i], ny = curr.y + dy[i];if (ins(nx, ny) && curr.f + c < d[nx][ny][1]) {d[nx][ny][1] = curr.f + c;pq.push({nx, ny, 1, curr.f + c});}if (curr.f + b < d[curr.x][curr.y][i]) {d[curr.x][curr.y][i] = curr.f + b;pq.push({curr.x, curr.y, i, curr.f + b});}}} else {int nx = curr.x + dx[curr.d], ny = curr.y + dy[curr.d];if (ins(nx, ny) && curr.f + a < d[nx][ny][curr.d]) {d[nx][ny][curr.d] = curr.f + a;pq.push({nx, ny, curr.d, curr.f + a});}if (curr.f < d[curr.x][curr.y][0]) {d[curr.x][curr.y][0] = curr.f;pq.push({curr.x, curr.y, 0, curr.f});}}}}ll ans = LLONG_MAX;FOR(i, 0, 6) ans = min(ans, d[dest.x][dest.y][i]);cout << ans;return 0;}

Compilation message (stderr)

soccer.cpp: In function 'int main()':
soccer.cpp:3:383: warning: 'dest.P::x' may be used uninitialized in this function [-Wmaybe-uninitialized]
 typedef long long ll;using namespace std;struct P {int x, y, d;ll f;};bool operator<(P A, P B) { return A.f > B.f; }int h, w;ll v[501][501], t[501][501], d[501][501][6];bool vis[501][501][6];int dx[6]{0, 0, 0, 0, 1, -1}, dy[6]{0, 0, 1, -1, 0, 0};bool ins(int x, int y) { return (~x && ~y && x <= h && y <= w); }int main() {ios_base::sync_with_stdio(0);cin.tie(0);int n;ll a, b, c;P dest;priority_queue<P> pq;cin >> h >> w >> a >> b >> c >> n;memset(v, 0x3f, sizeof(v));memset(t, 0x3f, sizeof(t));memset(d, 0x3f, sizeof(d));FOR(i, 0, n) {int x, y;cin >> x >> y;v[x][y] = 0;if (!i) pq.push({x, y, 1, 0}), d[x][y][1] = 0;if (i == n - 1) dest = {x, y, 0, 0};}FOR(i, 1, h + 1) FOR(j, 0, w + 1) {v[i][j] = min(v[i][j], v[i - 1][j] + 1);v[h - i][j] = min(v[h - i][j], v[h - i + 1][j] + 1);}FOR(i, 0, h + 1) FOR(j, 0, w + 1) FOR(k, 0, w + 1) {t[i][j] = min(t[i][j], v[i][k] + abs(j - k));}while (pq.size()) {P curr = pq.top();pq.pop();if (!vis[curr.x][curr.y][curr.d]) {vis[curr.x][curr.y][curr.d] = true;if (!curr.d) {if (curr.f + t[curr.x][curr.y] * c < d[curr.x][curr.y][1]) {d[curr.x][curr.y][1] = curr.f + t[curr.x][curr.y] * c;pq.push({curr.x, curr.y, 1, curr.f + t[curr.x][curr.y] * c});}} else if (curr.d == 1) {FOR(i, 2, 6) {int nx = curr.x + dx[i], ny = curr.y + dy[i];if (ins(nx, ny) && curr.f + c < d[nx][ny][1]) {d[nx][ny][1] = curr.f + c;pq.push({nx, ny, 1, curr.f + c});}if (curr.f + b < d[curr.x][curr.y][i]) {d[curr.x][curr.y][i] = curr.f + b;pq.push({curr.x, curr.y, i, curr.f + b});}}} else {int nx = curr.x + dx[curr.d], ny = curr.y + dy[curr.d];if (ins(nx, ny) && curr.f + a < d[nx][ny][curr.d]) {d[nx][ny][curr.d] = curr.f + a;pq.push({nx, ny, curr.d, curr.f + a});}if (curr.f < d[curr.x][curr.y][0]) {d[curr.x][curr.y][0] = curr.f;pq.push({curr.x, curr.y, 0, curr.f});}}}}ll ans = LLONG_MAX;FOR(i, 0, 6) ans = min(ans, d[dest.x][dest.y][i]);cout << ans;return 0;}
                                                                                                                                                                                                                                                                                                                                                                                               ^~~~
soccer.cpp:3:383: warning: 'dest.P::y' may be used uninitialized in this function [-Wmaybe-uninitialized]
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...