oj.uz

Submission #864561

# Submission time Handle Problem Language Result Execution time Memory
864561 2023-10-23T08:33:47 Z green_gold_dog Soccer (JOI17_soccer) C++17
100 / 100
 217 ms 20928 KB 
//#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

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);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 4560 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 158 ms 16696 KB Output is correct
4 Correct 165 ms 17584 KB Output is correct
5 Correct 32 ms 3420 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 18440 KB Output is correct
2 Correct 157 ms 17608 KB Output is correct
3 Correct 119 ms 15564 KB Output is correct
4 Correct 107 ms 16924 KB Output is correct
5 Correct 119 ms 17084 KB Output is correct
6 Correct 113 ms 18196 KB Output is correct
7 Correct 156 ms 18440 KB Output is correct
8 Correct 155 ms 17600 KB Output is correct
9 Correct 157 ms 18516 KB Output is correct
10 Correct 23 ms 3788 KB Output is correct
11 Correct 155 ms 17088 KB Output is correct
12 Correct 160 ms 17864 KB Output is correct
13 Correct 90 ms 16844 KB Output is correct
14 Correct 155 ms 18120 KB Output is correct
15 Correct 122 ms 15044 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 4560 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 158 ms 16696 KB Output is correct
4 Correct 165 ms 17584 KB Output is correct
5 Correct 32 ms 3420 KB Output is correct
6 Correct 187 ms 18440 KB Output is correct
7 Correct 157 ms 17608 KB Output is correct
8 Correct 119 ms 15564 KB Output is correct
9 Correct 107 ms 16924 KB Output is correct
10 Correct 119 ms 17084 KB Output is correct
11 Correct 113 ms 18196 KB Output is correct
12 Correct 156 ms 18440 KB Output is correct
13 Correct 155 ms 17600 KB Output is correct
14 Correct 157 ms 18516 KB Output is correct
15 Correct 23 ms 3788 KB Output is correct
16 Correct 155 ms 17088 KB Output is correct
17 Correct 160 ms 17864 KB Output is correct
18 Correct 90 ms 16844 KB Output is correct
19 Correct 155 ms 18120 KB Output is correct
20 Correct 122 ms 15044 KB Output is correct
21 Correct 34 ms 3672 KB Output is correct
22 Correct 198 ms 17084 KB Output is correct
23 Correct 178 ms 12148 KB Output is correct
24 Correct 210 ms 12740 KB Output is correct
25 Correct 187 ms 18552 KB Output is correct
26 Correct 190 ms 17856 KB Output is correct
27 Correct 145 ms 10308 KB Output is correct
28 Correct 126 ms 10980 KB Output is correct
29 Correct 189 ms 15428 KB Output is correct
30 Correct 113 ms 10888 KB Output is correct
31 Correct 164 ms 18152 KB Output is correct
32 Correct 217 ms 20928 KB Output is correct
33 Correct 145 ms 16848 KB Output is correct
34 Correct 202 ms 17076 KB Output is correct
35 Correct 104 ms 10864 KB Output is correct