oj.uz

Submission #930371

# Submission time Handle Problem Language Result Execution time Memory
930371 2024-02-19T13:29:22 Z vjudge1 Voting Cities (NOI22_votingcity) C++17
15 / 100
 90 ms 9160 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long

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>(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 9 ms 1884 KB Output is correct
2 Correct 5 ms 1628 KB Output is correct
3 Correct 9 ms 1884 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 9 ms 1884 KB Output is correct
2 Correct 5 ms 1628 KB Output is correct
3 Correct 9 ms 1884 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 57 ms 1944 KB Output is correct
7 Correct 50 ms 1688 KB Output is correct
8 Correct 90 ms 2156 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1884 KB Output is correct
2 Correct 5 ms 1628 KB Output is correct
3 Correct 9 ms 1884 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 57 ms 1944 KB Output is correct
7 Correct 50 ms 1688 KB Output is correct
8 Correct 90 ms 2156 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 49 ms 1884 KB Output is correct
12 Correct 43 ms 1688 KB Output is correct
13 Correct 47 ms 1880 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1884 KB Output is correct
2 Correct 5 ms 1628 KB Output is correct
3 Correct 9 ms 1884 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Runtime error 37 ms 9160 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 9 ms 1884 KB Output is correct
2 Correct 5 ms 1628 KB Output is correct
3 Correct 9 ms 1884 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 57 ms 1944 KB Output is correct
7 Correct 50 ms 1688 KB Output is correct
8 Correct 90 ms 2156 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Runtime error 37 ms 9160 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 46 ms 1880 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 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1884 KB Output is correct
2 Correct 5 ms 1628 KB Output is correct
3 Correct 9 ms 1884 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 57 ms 1944 KB Output is correct
7 Correct 50 ms 1688 KB Output is correct
8 Correct 90 ms 2156 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 49 ms 1884 KB Output is correct
12 Correct 43 ms 1688 KB Output is correct
13 Correct 47 ms 1880 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Runtime error 37 ms 9160 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -