Submission #684256

#TimeUsernameProblemLanguageResultExecution timeMemory
684256etheningSoccer (JOI17_soccer)C++17
0 / 100
131 ms86680 KiB
#include "bits/stdc++.h" #include <climits> #include <queue> #include <utility> using namespace std; using ll = long long; using pii = pair<int, int>; pii pos[100005]; int close[505][505]; // int dex[505][505][5]; vector<pair<int, int>> E[1255010]; int ans[1255010]; int dex(int x, int y, int z) { return (x * 501 + y) * 5 + z; } int main() { cin.tie(0)->sync_with_stdio(0); int h, w; cin >> h >> w; int A, B, C; cin >> A >> B >> C; int n; cin >> n; memset(close, -1, sizeof(close)); queue<pii> Q; for (int i = 0; i < n; i++) { cin >> pos[i].first >> pos[i].second; close[pos[i].first][pos[i].second] = 0; Q.push(pos[i]); } while (!Q.empty()) { auto [x, y] = Q.front(); Q.pop(); if (x > 0 && close[x - 1][y] == -1) { close[x - 1][y] = close[x][y] + 1; Q.push(make_pair(x - 1, y)); } if (x < h && close[x + 1][y] == -1) { close[x + 1][y] = close[x][y] + 1; Q.push(make_pair(x + 1, y)); } if (y > 0 && close[x][y - 1] == -1) { close[x][y - 1] = close[x][y] + 1; Q.push(make_pair(x, y - 1)); } if (y < w && close[x][y + 1] == -1) { close[x][y + 1] = close[x][y] + 1; Q.push(make_pair(x, y + 1)); } } for (int i = 0; i <= h; i++) { for (int j = 0; j <= w; j++) { for (int k = 0; k < 5; k++) { ans[dex(i, j, k)] = (ll)1e18; } } } for (int i = 0; i <= h; i++) { for (int j = 0; j <= w; j++) { E[dex(i, j, 0)].push_back(make_pair(dex(i, j, 1), B)); E[dex(i, j, 0)].push_back(make_pair(dex(i, j, 2), B)); E[dex(i, j, 0)].push_back(make_pair(dex(i, j, 3), B)); E[dex(i, j, 0)].push_back(make_pair(dex(i, j, 4), B)); E[dex(i, j, 1)].push_back(make_pair(dex(i, j, 0), close[i][j] * C)); E[dex(i, j, 2)].push_back(make_pair(dex(i, j, 0), close[i][j] * C)); E[dex(i, j, 3)].push_back(make_pair(dex(i, j, 0), close[i][j] * C)); E[dex(i, j, 4)].push_back(make_pair(dex(i, j, 0), close[i][j] * C)); if (i > 0) { E[dex(i, j, 0)].push_back(make_pair(dex(i - 1, j, 0), C)); E[dex(i, j, 1)].push_back(make_pair(dex(i - 1, j, 1), A)); } if (i < h) { E[dex(i, j, 0)].push_back(make_pair(dex(i + 1, j, 0), C)); E[dex(i, j, 2)].push_back(make_pair(dex(i + 1, j, 2), A)); } if (j > 0) { E[dex(i, j, 0)].push_back(make_pair(dex(i, j - 1, 0), C)); E[dex(i, j, 3)].push_back(make_pair(dex(i, j - 1, 3), A)); } if (j < w) { E[dex(i, j, 0)].push_back(make_pair(dex(i, j + 1, 0), C)); E[dex(i, j, 4)].push_back(make_pair(dex(i, j + 1, 4), A)); } } } // for (int i = 1; i <= cnt; i++) { // cout << "!" << (i - 1) / 5 + 1 << " " << (i - 1) % 5 << endl; // for (auto [to, weight] : E[i]) { // cout << (to - 1) / 5 + 1 << " " << (to - 1) % 5 << " " << weight << endl; // } // } int st = dex(pos[0].first, pos[0].second, 0); int ed = dex(pos[n - 1].first, pos[n - 1].second, 0); priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> PQ; ans[st] = 0; // cout << st << " " << ed << "!!!" << endl; PQ.push(make_pair(0, st)); while (!PQ.empty()) { auto [dist, cur] = PQ.top(); PQ.pop(); if (ans[cur] < dist) continue; if (cur == ed) break; for (auto [to, weight] : E[cur]) { if (ans[cur] + weight < ans[to]) { ans[to] = ans[cur] + weight; PQ.push(make_pair(ans[to], to)); // cout << cur << " " << to << " " << ans[to] << endl; } } } cout << ans[ed] << endl; }

Compilation message (stderr)

soccer.cpp: In function 'int main()':
soccer.cpp:60:25: warning: overflow in conversion from 'll' {aka 'long long int'} to 'int' changes value from '1000000000000000000' to '-1486618624' [-Woverflow]
   60 |     ans[dex(i, j, k)] = (ll)1e18;
      |                         ^~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...