Submission #1273066

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273066		ezrapo	Voting Cities (NOI22_votingcity)	C++20	100 / 100	400 ms	38396 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF=(1LL<<60);
int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, e, k; cin >> n >> e >> k;
    vector<int> voting(k);
    for (int i=0; i<k; i++) cin >> voting[i];
    vector<vector<pair<int, int>>> revG(32*n);
    for (int i=0; i<e; i++) {
        int u, v, c; cin >> u >> v >> c;
        for (int msk=0; msk<32; msk++) {
            int from=msk*n+v;
            revG[from].push_back({msk*n+u, c});
            for (int t=0; t<5; t++) {
                if (msk&(1<<t)) {
                    int prev=msk^(1<<t);
                    revG[from].push_back({prev*n+u, c*(10-t-1)/10});
                }
            }
        }
    }
    int q; cin >> q;
    vector<vector<int>> dist_msk(32, vector<int>(n, INF));
    for (int msk=0; msk<32; msk++) {
        vector<int> dist(32*n, INF);
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        for (int vc : voting) dist[msk*n+vc]=0, pq.push({0, msk*n+vc});
        while (!pq.empty()) {
            auto[d, node]=pq.top(); pq.pop();
            if (d!=dist[node]) continue;
            for (auto[child, d2] : revG[node]) {
                if (d+d2<dist[child]) {
                    dist[child]=d+d2;
                    pq.push({dist[child], child});
                }
            }
        }
        for (int c=0; c<n; c++) dist_msk[msk][c]=dist[c];
    }
    while (q--) {
        int s; vector<int> p(5);
        cin >> s >> p[0] >> p[1] >> p[2] >> p[3] >> p[4];
        int ans=INF;
        for (int msk=0; msk<32; msk++) {
            bool ok=true; int tc=0;
            for (int t=0; t<5; t++) {
                if (msk&(1<<t)) {
                    if (p[t]==-1) {ok=false; break;}
                    tc+=p[t];
                }
            }
            if (!ok) continue;
            int toll=dist_msk[msk][s];
            if (toll>=INF) continue;
            ans=min(ans, toll+tc);
        }
        cout << (ans>=INF?-1:ans) << "\n";
    }
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 10 / 10
• Subtask 7: 15 / 15
• Subtask 8: 50 / 50