oj.uz

Submission #916818

# Submission time Handle Problem Language Result Execution time Memory
916818 2024-01-26T14:44:01 Z maybe_baby Robot (JOI21_ho_t4) C++17
100 / 100
 418 ms 45504 KB 
#include <bits/stdc++.h>

#define x first
#define y second

using ll = long long;

using namespace std;

struct triple {
    int x, y;
    ll z;
};

struct four {
    int x, y;
    ll z, t;
};

int main() {
    int n, m;
    cin >> n >> m;
    int ans = 1;
    for (int i = 0; i < n * n; ++i) {
        ans *= 1032423;
        ans++;
    }
    vector<vector<four>> g(n);
    vector<vector<triple>> g1(n);
    for (int i = 0; i < m; i++) {
        int u, v, c;
        ll p;
        cin >> u >> v >> c >> p; u--; v--; c--;
        g1[u].push_back({v, c, p});
        g1[v].push_back({u, c, p});
    }
    vector<int> cnt(m, 0);
    vector<ll> sum(m, 0);
    for (int i = 0; i < n; i++) {
        for (auto [u, c, p] : g1[i]) {
            cnt[c]++;
            sum[c] += p;
        }
        for (auto [u, c, p] : g1[i]) {
            if (cnt[c] > 1) {
                g[i].push_back({u, c, p, sum[c] - p});
            } else {
                g[i].push_back({u, c, p, 0});
            }
        }
        for (auto [u, c, p] : g1[i]) {
            cnt[c]--;
            sum[c] -= p;
        }
    }
    set<pair<ll, int>> st;
    vector<ll> dist(n, INT64_MAX / 2), dist2(m, INT64_MAX / 2);
    vector<int> used(n, 0);
    dist[0] = 0;
    for (int i = 0; i < n; i++) {
        st.emplace(dist[i], i);
    }
    while (!st.empty()) {
        auto [d, s] = *st.begin();
        st.erase(st.begin());
        for (auto [i, c, p, w] : g[s]) {
            if (used[i]) {
                dist2[c] = min(dist[i], dist2[c]);
            }
        }
        used[s] = 1;
        for (auto [i, c, p, w] : g[s]) {
            if (!used[i]) {
                st.erase({dist[i], i});
                dist[i] = min(dist[i], min({d + w, dist2[c] + w, d + p}));
                st.emplace(dist[i], i);
            }
        }
        for (auto [i, c, p, w] : g[s]) {
            if (used[i]) {
                dist2[c] = INT64_MAX / 2;
            }
        }
    }
    if (dist[n - 1] == INT64_MAX / 2) {
        cout << "-1\n";
    } else {
        cout << dist[n - 1] << "\n";
    }
}

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 424 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 2 ms 712 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 3 ms 604 KB Output is correct
13 Correct 3 ms 604 KB Output is correct
14 Correct 2 ms 704 KB Output is correct
15 Correct 2 ms 600 KB Output is correct
16 Correct 3 ms 860 KB Output is correct
17 Correct 2 ms 604 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 3 ms 604 KB Output is correct
20 Correct 4 ms 604 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 15440 KB Output is correct
2 Correct 47 ms 7760 KB Output is correct
3 Correct 171 ms 22996 KB Output is correct
4 Correct 73 ms 11344 KB Output is correct
5 Correct 310 ms 39736 KB Output is correct
6 Correct 312 ms 40352 KB Output is correct
7 Correct 313 ms 39968 KB Output is correct
8 Correct 409 ms 43808 KB Output is correct
9 Correct 344 ms 44024 KB Output is correct
10 Correct 185 ms 25424 KB Output is correct
11 Correct 179 ms 25172 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 424 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 2 ms 712 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 3 ms 604 KB Output is correct
13 Correct 3 ms 604 KB Output is correct
14 Correct 2 ms 704 KB Output is correct
15 Correct 2 ms 600 KB Output is correct
16 Correct 3 ms 860 KB Output is correct
17 Correct 2 ms 604 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 3 ms 604 KB Output is correct
20 Correct 4 ms 604 KB Output is correct
21 Correct 120 ms 15440 KB Output is correct
22 Correct 47 ms 7760 KB Output is correct
23 Correct 171 ms 22996 KB Output is correct
24 Correct 73 ms 11344 KB Output is correct
25 Correct 310 ms 39736 KB Output is correct
26 Correct 312 ms 40352 KB Output is correct
27 Correct 313 ms 39968 KB Output is correct
28 Correct 409 ms 43808 KB Output is correct
29 Correct 344 ms 44024 KB Output is correct
30 Correct 185 ms 25424 KB Output is correct
31 Correct 179 ms 25172 KB Output is correct
32 Correct 178 ms 22760 KB Output is correct
33 Correct 165 ms 20816 KB Output is correct
34 Correct 249 ms 27704 KB Output is correct
35 Correct 213 ms 24136 KB Output is correct
36 Correct 224 ms 31040 KB Output is correct
37 Correct 249 ms 36520 KB Output is correct
38 Correct 294 ms 40156 KB Output is correct
39 Correct 222 ms 30528 KB Output is correct
40 Correct 382 ms 45140 KB Output is correct
41 Correct 402 ms 45504 KB Output is correct
42 Correct 418 ms 40232 KB Output is correct
43 Correct 136 ms 18256 KB Output is correct
44 Correct 287 ms 34552 KB Output is correct
45 Correct 278 ms 36688 KB Output is correct
46 Correct 273 ms 35852 KB Output is correct
47 Correct 269 ms 34072 KB Output is correct
48 Correct 331 ms 40696 KB Output is correct