Submission #1281834

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281834		cheska	Voting Cities (NOI22_votingcity)	C++20	100 / 100	70 ms	8448 KiB

Main

//dominater orz
//evenvalue orz
//roumak orz
//melody orz
//cpp orz
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define ppii pair<pii, pii> 
#define tiii tuple<int, int, int>
#define g0 get<0>
#define g1 get<1>
#define g2 get<2>
#define f first
#define s second
#define pb push_back
const int N = 2e5+5;
const int MOD = 1e9+7;
struct state {
    int d, m, u;
};
struct comp {
    bool operator()(const state &a, const state &b) const {
        return a.d > b.d;
    }
};
signed main() {
  //  freopen("in.in", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m, k; cin >> n >> m >> k;
    vector<int> t;
    for (int i = 0; i < k; i++) {
        int j; cin >> j; t.pb(j);
    }
    vector<vector<pii>> a(n);
    while (m--) {
        int u, v, w; cin >> u >> v >> w;
        a[v].pb({u, w});
    }
    vector<vector<int>> ans(32, vector<int>(n, LLONG_MAX));
    priority_queue<state, vector<state>, comp> pq;
    for (int i : t) {
        pq.push({0, 0, i});
        ans[0][i] = 0;
    }
    while (!pq.empty()) {
        auto [d, m, u] = pq.top(); pq.pop();
        if (d > ans[m][u]) continue;
        for (pii v : a[u]) {
            if (ans[m][v.f] > d+v.s) {
                ans[m][v.f] = d+v.s;
                pq.push({ans[m][v.f], m, v.f});
            }
            for (int i = 0; i < 5; i++) {
                if (!(m&(1<<i))) {
                    int x = (10-i-1)*v.s/10;
                    if (ans[m+(1<<i)][v.f] > d+x) {
                        ans[m+(1<<i)][v.f] = d+x;
                        pq.push({d+x, m+(1<<i), v.f});
                    }
                }
            }
        }
    }
    int q; cin >> q;
    while (q--) {
        int u; cin >> u;
        vector<int> p(5);
        int ans2 = LLONG_MAX;
        for (int i = 0; i < 5; i++) cin >> p[i];
        for (int i = 0; i < 32; i++) {
            if (ans[i][u] == LLONG_MAX) continue;
            bool ch = true; int k = 0;
            for (int j = 0; j < 5; j++) {
                if (i&(1<<j)) {
                    if (p[j] == -1) {ch = false; break;}
                    k += p[j];
                }
            }
            if (!ch) continue;
            ans2 = min(ans2, ans[i][u]+k);
        }
        if (ans2 == LLONG_MAX) cout << "-1\n";
        else cout << ans2 << '\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