oj.uz

Submission #937897

# Submission time Handle Problem Language Result Execution time Memory
937897 2024-03-04T16:23:01 Z zwezdinv Robot (JOI21_ho_t4) C++17
0 / 100
 366 ms 40060 KB 
#include <bits/stdc++.h>

struct edge {
        int to, col;
        long long cost = 0;
        edge() = default;
        edge(int to, int col, long long cost) : to(to), col(col), cost(cost) {}
};

int main() {
        std::cin.tie(nullptr)->sync_with_stdio(false);

        int n, m;
        std::cin >> n >> m;
        std::vector<std::vector<edge>> g(n);
        std::vector<std::map<int, long long>> mp(n);
        for (int i = 0; i < m; ++i) {
                int u, v, c;
                long long p;
                std::cin >> u >> v >> c >> p;
                --u, --v;
                mp[u][c] += p;
                mp[v][c] += p;
                g[u].emplace_back(v, c, p);
                g[v].emplace_back(u, c, p);
        }
        std::vector<long long> dist(n, 1e18);
        dist[0] = 0;
        std::set<std::pair<long long, int>> st;
        st.emplace(0, 0);
        while (st.size()) {
                int u = st.begin()->second;
                st.erase(st.begin());
                for (auto [to, col, cost] : g[u]) {
                        long long w = std::min(cost, mp[u][col] - cost);
                        if (dist[to] > dist[u] + w) {
                                st.erase({dist[to], to});
                                dist[to] = dist[u] + w;
                                st.emplace(dist[to], to);
                        }
                }
        }
        if (dist[n - 1] == 1e18) std::cout << -1;
        else std::cout << dist[n - 1];
}

Subtask #1
0 / 34.0

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

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 12980 KB Output is correct
2 Correct 23 ms 6736 KB Output is correct
3 Correct 76 ms 14484 KB Output is correct
4 Correct 34 ms 9432 KB Output is correct
5 Incorrect 366 ms 40060 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

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