oj.uz

Submission #930369

# Submission time Handle Problem Language Result Execution time Memory
930369 2024-02-19T13:25:08 Z vjudge1 Voting Cities (NOI22_votingcity) C++17
15 / 100
 86 ms 7364 KB 
#include <bits/stdc++.h>

using namespace std;


int main() {
    int n, e, special;
    cin >> n >> e >> special;

    vector<bool> is_special(n, false);
    for (int i = 0; i < special; i++) {
        int x;
        cin >> x;
        is_special[x] = true;
    }

    vector<vector<pair<int, long long>>> g(n), rev_g(n);

    for (int i = 0; i < e; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].emplace_back(v, w);
        rev_g[v].emplace_back(u, w);
    }

    int q;
    cin >> q;


    while (q--) {

        int source;
        cin >> source;
        int mask = 0;
        vector<long long> prices;

        for (int i = 0; i < 5; i++) {
            int x;
            cin >> x;
            if (x != -1) mask |= (1 << i);
            prices.push_back(x);
        }

        // totalCost, mask, source
        priority_queue<pair<long long, pair<int, int>>, vector<pair<long long, pair<int, int>>>, greater<>> pq;
        pq.push({0, {0, source}});

        vector<vector<long long>> dist(n, vector<long long>(5, 0));
        vector<vector<bool>> visited(n, vector<bool>(5, 0));

        long long answer = -1;

        while (!pq.empty()) {
            auto [totalCost, state] = pq.top();
            pq.pop();

            if (visited[state.second][state.first]) continue;
            visited[state.second][state.first] = 1;
            dist[state.second][state.first] = totalCost;

            if (is_special[state.second]) {
                answer = totalCost;
                break;
            }

            for (auto [v, w]: g[state.second]) {
                if (!dist[v][state.first] || dist[v][state.first] > totalCost + w) {
                    pq.push({totalCost + w, {state.first, v}});
                }
            }

            for (int i = 0; i < 5; i++) {
                if (mask & (1 << i) && (!(state.first & (1 << i)))) {
                    for (auto [v, w]: g[state.second]) {
                        int newMask = state.first | (1 << i);
                        long long new_cost = 1LL * (w * 10 - w * (i + 1)) / 10LL + prices[i];


                        if (!visited[v][newMask] || dist[v][newMask] > totalCost + new_cost) {
                            pq.push({totalCost + new_cost, {newMask, v}});
                        }
                    }
                }
            }
        }

        cout << answer << endl;

    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1884 KB Output is correct
2 Correct 5 ms 1628 KB Output is correct
3 Correct 13 ms 1976 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1884 KB Output is correct
2 Correct 5 ms 1628 KB Output is correct
3 Correct 13 ms 1976 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 58 ms 2112 KB Output is correct
7 Correct 55 ms 1688 KB Output is correct
8 Correct 86 ms 2140 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1884 KB Output is correct
2 Correct 5 ms 1628 KB Output is correct
3 Correct 13 ms 1976 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 58 ms 2112 KB Output is correct
7 Correct 55 ms 1688 KB Output is correct
8 Correct 86 ms 2140 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 45 ms 1944 KB Output is correct
12 Correct 50 ms 1688 KB Output is correct
13 Correct 46 ms 1944 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1884 KB Output is correct
2 Correct 5 ms 1628 KB Output is correct
3 Correct 13 ms 1976 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Runtime error 35 ms 7364 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1884 KB Output is correct
2 Correct 5 ms 1628 KB Output is correct
3 Correct 13 ms 1976 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 58 ms 2112 KB Output is correct
7 Correct 55 ms 1688 KB Output is correct
8 Correct 86 ms 2140 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Runtime error 35 ms 7364 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 1944 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 860 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #8
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1884 KB Output is correct
2 Correct 5 ms 1628 KB Output is correct
3 Correct 13 ms 1976 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 58 ms 2112 KB Output is correct
7 Correct 55 ms 1688 KB Output is correct
8 Correct 86 ms 2140 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 45 ms 1944 KB Output is correct
12 Correct 50 ms 1688 KB Output is correct
13 Correct 46 ms 1944 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Runtime error 35 ms 7364 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -