oj.uz

Submission #746213

# Submission time Handle Problem Language Result Execution time Memory
746213 2023-05-21T22:39:48 Z stevancv Robot (JOI21_ho_t4) C++14
58 / 100
 3000 ms 86856 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 1e5 + 2;
const ll linf = 1e18;
map<int, vector<array<int, 2>>> g[N];
map<int, ll> sum[N], dist[N];
int col[2 * N], cost[2 * N];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v >> col[i] >> cost[i];
        g[u][col[i]].push_back({v, i});
        g[v][col[i]].push_back({u, i});
        dist[u][col[i]] = dist[v][col[i]] = linf;
        sum[u][col[i]] += cost[i];
        sum[v][col[i]] += cost[i];
    }
    for (int i = 2; i <= n; i++) dist[i][0] = linf;
    priority_queue<pair<ll, pair<int, int>>> pq;
    pq.push({0, {1, 0}});
    dist[1][0] = 0;
    while (!pq.empty()) {
        ll d = -pq.top().first;
        int x = pq.top().second.first;
        int y = pq.top().second.second;
        pq.pop();
        if (y > 0) {
            for (auto u : g[x][y]) {
                ll o = d + sum[x][y] - cost[u[1]];
                if (dist[u[0]][0] > o) {
                    dist[u[0]][0] = o;
                    pq.push({-o, {u[0], 0}});
                }
            }
            continue;
        }
        for (auto uu : g[x]) {
            int y = uu.first;
            for (auto u : uu.second) {
                ll o = d + min((ll)cost[u[1]], sum[x][y] - cost[u[1]]);
                if (dist[u[0]][0] > o) {
                    dist[u[0]][0] = o;
                    pq.push({-o, {u[0], 0}});
                }
                if (dist[u[0]][y] > d) {
                    dist[u[0]][y] = d;
                    pq.push({-d, {u[0], y}});
                }
            }
        }
    }
    if (dist[n][0] == linf) dist[n][0] = -1;
    cout << dist[n][0] << en;
    return 0;
}

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 9 ms 14368 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 13 ms 14420 KB Output is correct
5 Correct 8 ms 14420 KB Output is correct
6 Correct 7 ms 14416 KB Output is correct
7 Correct 16 ms 14564 KB Output is correct
8 Correct 10 ms 14432 KB Output is correct
9 Correct 11 ms 15060 KB Output is correct
10 Correct 10 ms 14996 KB Output is correct
11 Correct 9 ms 14804 KB Output is correct
12 Correct 8 ms 14792 KB Output is correct
13 Correct 9 ms 14804 KB Output is correct
14 Correct 19 ms 14812 KB Output is correct
15 Correct 8 ms 14760 KB Output is correct
16 Correct 9 ms 14804 KB Output is correct
17 Correct 9 ms 14804 KB Output is correct
18 Correct 8 ms 14696 KB Output is correct
19 Correct 9 ms 14676 KB Output is correct
20 Correct 17 ms 14680 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 35612 KB Output is correct
2 Correct 94 ms 25560 KB Output is correct
3 Correct 329 ms 31116 KB Output is correct
4 Correct 150 ms 28744 KB Output is correct
5 Correct 1088 ms 86856 KB Output is correct
6 Correct 815 ms 75764 KB Output is correct
7 Correct 385 ms 56224 KB Output is correct
8 Correct 439 ms 53580 KB Output is correct
9 Correct 470 ms 53604 KB Output is correct
10 Correct 410 ms 52076 KB Output is correct
11 Correct 224 ms 40832 KB Output is correct

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 9 ms 14368 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 13 ms 14420 KB Output is correct
5 Correct 8 ms 14420 KB Output is correct
6 Correct 7 ms 14416 KB Output is correct
7 Correct 16 ms 14564 KB Output is correct
8 Correct 10 ms 14432 KB Output is correct
9 Correct 11 ms 15060 KB Output is correct
10 Correct 10 ms 14996 KB Output is correct
11 Correct 9 ms 14804 KB Output is correct
12 Correct 8 ms 14792 KB Output is correct
13 Correct 9 ms 14804 KB Output is correct
14 Correct 19 ms 14812 KB Output is correct
15 Correct 8 ms 14760 KB Output is correct
16 Correct 9 ms 14804 KB Output is correct
17 Correct 9 ms 14804 KB Output is correct
18 Correct 8 ms 14696 KB Output is correct
19 Correct 9 ms 14676 KB Output is correct
20 Correct 17 ms 14680 KB Output is correct
21 Correct 237 ms 35612 KB Output is correct
22 Correct 94 ms 25560 KB Output is correct
23 Correct 329 ms 31116 KB Output is correct
24 Correct 150 ms 28744 KB Output is correct
25 Correct 1088 ms 86856 KB Output is correct
26 Correct 815 ms 75764 KB Output is correct
27 Correct 385 ms 56224 KB Output is correct
28 Correct 439 ms 53580 KB Output is correct
29 Correct 470 ms 53604 KB Output is correct
30 Correct 410 ms 52076 KB Output is correct
31 Correct 224 ms 40832 KB Output is correct
32 Correct 207 ms 26196 KB Output is correct
33 Correct 278 ms 29392 KB Output is correct
34 Correct 622 ms 51748 KB Output is correct
35 Correct 430 ms 43228 KB Output is correct
36 Correct 387 ms 49716 KB Output is correct
37 Correct 773 ms 52120 KB Output is correct
38 Correct 455 ms 59900 KB Output is correct
39 Correct 328 ms 28872 KB Output is correct
40 Correct 479 ms 55080 KB Output is correct
41 Correct 541 ms 55160 KB Output is correct
42 Correct 658 ms 67020 KB Output is correct
43 Correct 305 ms 39260 KB Output is correct
44 Correct 671 ms 41264 KB Output is correct
45 Correct 411 ms 51376 KB Output is correct
46 Correct 334 ms 51148 KB Output is correct
47 Execution timed out 3039 ms 52060 KB Time limit exceeded
48 Halted 0 ms 0 KB -