oj.uz

Submission #930373

# Submission time Handle Problem Language Result Execution time Memory
930373 2024-02-19T13:33:33 Z vjudge1 Voting Cities (NOI22_votingcity) C++17
45 / 100
 1000 ms 11680 KB 
#include <bits/stdc++.h>

using namespace std;


signed 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>((1 << 5) + 1, 0));
        vector<vector<bool>> visited(n, vector<bool>((1<<5) + 1, 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 9 ms 2908 KB Output is correct
2 Correct 5 ms 2628 KB Output is correct
3 Correct 9 ms 2908 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2908 KB Output is correct
2 Correct 5 ms 2628 KB Output is correct
3 Correct 9 ms 2908 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 71 ms 2964 KB Output is correct
7 Correct 70 ms 2712 KB Output is correct
8 Correct 98 ms 2964 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 9 ms 2908 KB Output is correct
2 Correct 5 ms 2628 KB Output is correct
3 Correct 9 ms 2908 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 71 ms 2964 KB Output is correct
7 Correct 70 ms 2712 KB Output is correct
8 Correct 98 ms 2964 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 57 ms 2968 KB Output is correct
12 Correct 61 ms 2708 KB Output is correct
13 Correct 61 ms 2984 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 344 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2908 KB Output is correct
2 Correct 5 ms 2628 KB Output is correct
3 Correct 9 ms 2908 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 117 ms 8840 KB Output is correct
7 Correct 10 ms 2652 KB Output is correct
8 Correct 17 ms 4184 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2908 KB Output is correct
2 Correct 5 ms 2628 KB Output is correct
3 Correct 9 ms 2908 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 71 ms 2964 KB Output is correct
7 Correct 70 ms 2712 KB Output is correct
8 Correct 98 ms 2964 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 117 ms 8840 KB Output is correct
12 Correct 10 ms 2652 KB Output is correct
13 Correct 17 ms 4184 KB Output is correct
14 Execution timed out 1053 ms 11680 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 2964 KB Output is correct
2 Correct 58 ms 3164 KB Output is correct
3 Correct 54 ms 2712 KB Output is correct
4 Correct 76 ms 3224 KB Output is correct

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 600 KB Output is correct
2 Correct 4 ms 604 KB Output is correct
3 Correct 6 ms 348 KB Output is correct
4 Correct 3 ms 604 KB Output is correct
5 Correct 3 ms 348 KB Output is correct
6 Correct 3 ms 348 KB Output is correct
7 Correct 3 ms 604 KB Output is correct
8 Correct 3 ms 348 KB Output is correct

Subtask #8
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2908 KB Output is correct
2 Correct 5 ms 2628 KB Output is correct
3 Correct 9 ms 2908 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 71 ms 2964 KB Output is correct
7 Correct 70 ms 2712 KB Output is correct
8 Correct 98 ms 2964 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 57 ms 2968 KB Output is correct
12 Correct 61 ms 2708 KB Output is correct
13 Correct 61 ms 2984 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 117 ms 8840 KB Output is correct
17 Correct 10 ms 2652 KB Output is correct
18 Correct 17 ms 4184 KB Output is correct
19 Execution timed out 1053 ms 11680 KB Time limit exceeded
20 Halted 0 ms 0 KB -