oj.uz

Submission #930374

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

using namespace std;


signed main() {
    
    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(0);
    
    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 5 ms 2904 KB Output is correct
2 Correct 3 ms 2648 KB Output is correct
3 Correct 5 ms 2908 KB Output is correct
4 Correct 0 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 5 ms 2904 KB Output is correct
2 Correct 3 ms 2648 KB Output is correct
3 Correct 5 ms 2908 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 76 ms 2968 KB Output is correct
7 Correct 72 ms 2800 KB Output is correct
8 Correct 96 ms 2964 KB Output is correct
9 Correct 0 ms 344 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 5 ms 2904 KB Output is correct
2 Correct 3 ms 2648 KB Output is correct
3 Correct 5 ms 2908 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 76 ms 2968 KB Output is correct
7 Correct 72 ms 2800 KB Output is correct
8 Correct 96 ms 2964 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 55 ms 2908 KB Output is correct
12 Correct 66 ms 3072 KB Output is correct
13 Correct 59 ms 2852 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2904 KB Output is correct
2 Correct 3 ms 2648 KB Output is correct
3 Correct 5 ms 2908 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 104 ms 7888 KB Output is correct
7 Correct 7 ms 2648 KB Output is correct
8 Correct 12 ms 4152 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2904 KB Output is correct
2 Correct 3 ms 2648 KB Output is correct
3 Correct 5 ms 2908 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 76 ms 2968 KB Output is correct
7 Correct 72 ms 2800 KB Output is correct
8 Correct 96 ms 2964 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 104 ms 7888 KB Output is correct
12 Correct 7 ms 2648 KB Output is correct
13 Correct 12 ms 4152 KB Output is correct
14 Execution timed out 1068 ms 10612 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 2968 KB Output is correct
2 Correct 55 ms 2908 KB Output is correct
3 Correct 55 ms 2712 KB Output is correct
4 Correct 74 ms 3136 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 600 KB Output is correct
3 Correct 6 ms 424 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 3 ms 348 KB Output is correct
7 Correct 3 ms 600 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 5 ms 2904 KB Output is correct
2 Correct 3 ms 2648 KB Output is correct
3 Correct 5 ms 2908 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 76 ms 2968 KB Output is correct
7 Correct 72 ms 2800 KB Output is correct
8 Correct 96 ms 2964 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 55 ms 2908 KB Output is correct
12 Correct 66 ms 3072 KB Output is correct
13 Correct 59 ms 2852 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 104 ms 7888 KB Output is correct
17 Correct 7 ms 2648 KB Output is correct
18 Correct 12 ms 4152 KB Output is correct
19 Execution timed out 1068 ms 10612 KB Time limit exceeded
20 Halted 0 ms 0 KB -