Submission #864561

#TimeUsernameProblemLanguageResultExecution timeMemory
864561green_gold_dogSoccer (JOI17_soccer)C++17
100 / 100
217 ms20928 KiB
//#pragma GCC optimize("Ofast") //#pragma GCC target("avx,avx2,sse,sse2,sse3,ssse3,sse4,abm,popcnt,mmx") #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef double db; typedef long double ldb; typedef complex<double> cd; constexpr ll INF64 = 9'000'000'000'000'000'000, INF32 = 2'000'000'000, MOD = 1'000'000'007; constexpr db PI = acos(-1); constexpr bool IS_FILE = false, IS_TEST_CASES = false; random_device rd; mt19937 rnd32(rd()); mt19937_64 rnd64(rd()); template<typename T> bool assign_max(T& a, T b) { if (b > a) { a = b; return true; } return false; } template<typename T> bool assign_min(T& a, T b) { if (b < a) { a = b; return true; } return false; } template<typename T> T square(T a) { return a * a; } template<> struct std::hash<pair<ll, ll>> { ll operator() (pair<ll, ll> p) const { return ((__int128)p.first * MOD + p.second) % INF64; } }; void solve() { ll h, w; cin >> h >> w; h++; w++; ll a, b, c; cin >> a >> b >> c; ll n; cin >> n; vector<pair<ll, ll>> arr; for (ll i = 0; i < n; i++) { ll x, y; cin >> x >> y; arr.emplace_back(x, y); } vector<vector<ll>> dist(h, vector<ll>(w, INF64)); queue<pair<ll, ll>> q; for (auto[x, y] : arr) { q.emplace(x, y); dist[x][y] = 0; } vector<pair<ll, ll>> go1, go2, go3; go1.emplace_back(-1, 0); go1.emplace_back(1, 0); go2.emplace_back(0, -1); go2.emplace_back(0, 1); go3.emplace_back(0, 1); go3.emplace_back(0, -1); go3.emplace_back(1, 0); go3.emplace_back(-1, 0); while (!q.empty()) { auto[x, y] = q.front(); q.pop(); for (auto[ax, ay] : go3) { if (x + ax >= 0 && y + ay >= 0 && x + ax < h && y + ay < w && assign_min(dist[x + ax][y + ay], dist[x][y] + c)) { q.emplace(x + ax, y + ay); } } } vector<vector<ll>> d1(h, vector<ll>(w, INF64)), dx(h, vector<ll>(w, INF64)), dy(h, vector<ll>(w, INF64)); d1[arr[0].first][arr[0].second] = 0; priority_queue<tuple<ll, ll, ll, ll>, vector<tuple<ll, ll, ll, ll>>, greater<tuple<ll, ll, ll, ll>>> qq; qq.emplace(0, 0, arr[0].first, arr[0].second); while (!qq.empty()) { auto[d, t, x, y] = qq.top(); qq.pop(); if (t == 0) { if (d1[x][y] != d) { continue; } if (assign_min(dx[x][y], d + b)) { qq.emplace(d + b, 1, x, y); } if (assign_min(dy[x][y], d + b)) { qq.emplace(d + b, 2, x, y); } for (auto[ax, ay] : go3) { if (x + ax >= 0 && y + ay >= 0 && x + ax < h && y + ay < w && assign_min(d1[x + ax][y + ay], d + c)) { qq.emplace(d + c, 0, x + ax, y + ay); } } } if (t == 1) { if (dx[x][y] != d) { continue; } if (assign_min(d1[x][y], d + dist[x][y])) { qq.emplace(d1[x][y], 0, x, y); } for (auto[ax, ay] : go1) { if (x + ax >= 0 && x + ax < h && assign_min(dx[x + ax][y + ay], d + a)) { qq.emplace(d + a, 1, x + ax, y + ay); } } } if (t == 2) { if (dy[x][y] != d) { continue; } if (assign_min(d1[x][y], d + dist[x][y])) { qq.emplace(d1[x][y], 0, x, y); } for (auto[ax, ay] : go2) { if (y + ay >= 0 && y + ay < w && assign_min(dy[x + ax][y + ay], d + a)) { qq.emplace(d + a, 2, x + ax, y + ay); } } } } cout << d1[arr.back().first][arr.back().second] << '\n'; } int main() { if (IS_FILE) { freopen("", "r", stdin); freopen("", "w", stdout); } ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); ll t = 1; if (IS_TEST_CASES) { cin >> t; } for (ll i = 0; i < t; i++) { solve(); } }

Compilation message (stderr)

soccer.cpp: In function 'int main()':
soccer.cpp:144:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  144 |                 freopen("", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~
soccer.cpp:145:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  145 |                 freopen("", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...