oj.uz

Submission #930413

# Submission time Handle Problem Language Result Execution time Memory
930413 2024-02-19T14:57:22 Z vjudge1 Voting Cities (NOI22_votingcity) C++17
0 / 100
 80 ms 7260 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);
    }

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

    priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<>> pq;
    // totalCost, mask, node

    for (int i = 0; i < n; i++)
        if (is_special[i]) {
            pq.push({0, {0, i}});
        }

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

        auto [mask, node] = state;

        if (visited[node][mask]) continue;
        visited[node][mask] = true;

        dist[node][mask] = totalCost;

        for (auto [v, w]: rev_g[node]) {
            for (int bit = 0; bit < 5; bit++) {
                bool isSet = mask & (1 << bit);
                if (isSet) continue;

                int newMask = mask | (1 << bit);

                if (visited[v][newMask]) continue;

                long long newPrice = (w * 10 - w * (bit + 1)) / 10 + totalCost;

                if (!visited[v][newMask]) {
                    pq.push({newPrice, {newMask, v}});
                }
            }
        }

        for (auto [v, w]: rev_g[node]) {
            if (visited[v][mask]) continue;
            long long newPrice = w + totalCost;
            pq.push({newPrice, {mask, v}});
        }
    }


    int q;
    cin >> q;

    while (q--) {
        int src;
        cin >> src;

        vector<int> ticket_price(5);
        for (int i = 0; i < 5; i++) cin >> ticket_price[i];


        long long ans = 1e16;


        for (long long i = 0, tmp = 0; i < (1 << 5); i++) {
            if (visited[src][i]) {
                for (int j = 0; j < 5; j++) {
                    if (i & (1 << j)) {
                        if (ticket_price[j] == -1) {
                            tmp = 1e16;
                            break;
                        } else tmp += ticket_price[j];
                    }
                }
                ans = min(ans, tmp + dist[src][i]);
            }

            tmp = 0;
        }

        if (ans >= 1e16) cout << -1 << '\n';
        else cout << ans << '\n';
    }
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 5.0

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

Subtask #4
0 / 5.0

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

Subtask #5
0 / 5.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1368 KB Output is correct
2 Correct 10 ms 1368 KB Output is correct
3 Incorrect 1 ms 456 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 50.0

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