oj.uz

Submission #385034

# Submission time Handle Problem Language Result Execution time Memory
385034 2021-04-03T03:09:30 Z timmyfeng Robot (JOI21_ho_t4) C++17
24 / 100
 970 ms 65436 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 100001;

map<int, vector<array<long long, 2>>> adj[N];
priority_queue<array<long long, 3>> que;
map<int, long long> dist[N];

void update(int c, int x, int d) {
    if (dist[c].count(x) == 0 || d < dist[c][x]) {
        que.push({-d, c, x});
        dist[c][x] = d;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    while (m--) {
        int u, v, c, p;
        cin >> u >> v >> c >> p;
        adj[u][c].push_back({v, p});
        adj[v][c].push_back({u, p});
    }

    que.push({0, 1, 0});
    dist[1][0] = 0;

    while (!que.empty()) {
        auto [d, u, x] = que.top();
        que.pop();
        d = -d;

        if (d > dist[u][x]) {
            continue;
        }

        if (x == 0) {
            for (auto &[y, v] : adj[u]) {
                long long sum = 0;
                for (auto [c, w] : v) {
                    sum += w;
                }

                for (auto [c, w] : v) {
                    update(c, 0, d + min(w, sum - w));
                    update(c, y, d);
                }
            }
        } else {
            long long sum = 0;
            for (auto [c, w] : adj[u][x]) {
                sum += w;
            }

            for (auto [c, w] : adj[u][x]) {
                update(c, 0, d + sum - w);
            }
        }
    }

    cout << (dist[n].count(0) == 0 ? -1 : dist[n][0]) << "\n";
}

Subtask #1
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9708 KB Output is correct
2 Correct 7 ms 9708 KB Output is correct
3 Correct 8 ms 9708 KB Output is correct
4 Correct 7 ms 9708 KB Output is correct
5 Correct 8 ms 9708 KB Output is correct
6 Incorrect 7 ms 9708 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 26144 KB Output is correct
2 Correct 86 ms 18488 KB Output is correct
3 Correct 241 ms 23780 KB Output is correct
4 Correct 137 ms 21372 KB Output is correct
5 Correct 970 ms 65436 KB Output is correct
6 Correct 709 ms 60548 KB Output is correct
7 Correct 383 ms 48196 KB Output is correct
8 Correct 422 ms 45292 KB Output is correct
9 Correct 450 ms 45420 KB Output is correct
10 Correct 347 ms 37792 KB Output is correct
11 Correct 113 ms 22764 KB Output is correct

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9708 KB Output is correct
2 Correct 7 ms 9708 KB Output is correct
3 Correct 8 ms 9708 KB Output is correct
4 Correct 7 ms 9708 KB Output is correct
5 Correct 8 ms 9708 KB Output is correct
6 Incorrect 7 ms 9708 KB Output isn't correct
7 Halted 0 ms 0 KB -