Submission #758888

#	Time	Username	Problem	Language	Result	Execution time	Memory
758888		ProtonDecay314	Voting Cities (NOI22_votingcity)	C++17	100 / 100	350 ms	93796 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;

struct node {
    ll i;
    ll S;
    ll ind() {
        return (i << 5ll) | S;
    }
};

node node_from_ind(ll ind) {
    node e = {ind >> 5ll, ind & 0b11111};
    return e;
}

int main() {
    ll n, e, k;
    cin >> n >> e >> k;
    const ll num_tickets = 5ll;
    const ll ticket_combs = 1ll << num_tickets;

    vector<vector<pll>> out_adj;
    vector<vector<pll>> in_adj;
    out_adj.reserve(n * ticket_combs);
    in_adj.reserve(n * ticket_combs);
    for(ll i = 0ll; i < n * ticket_combs; i++) {
        vector<pll> out_row;
        vector<pll> in_row;
        out_adj.push_back(out_row);
        in_adj.push_back(in_row);
    }

    vector<ll> v_cities;
    for(ll i = 0; i < k; i++) {
        ll curcity;
        cin >> curcity;
        curcity <<= num_tickets;
        for(ll j = 0ll; j < ticket_combs; j++) {
            v_cities.push_back(curcity | j);
        }
    }

    // Build the graph
    for(ll i = 0ll; i < e; i++) {
        ll u, v, c;
        cin >> u >> v >> c;

        for(ll tickets = 0ll; tickets < ticket_combs; tickets++) {
            out_adj[(u << num_tickets) | tickets].push_back({(v << num_tickets) | tickets, c});
            in_adj[(v << num_tickets) | tickets].push_back({(u << num_tickets) | tickets, c});

            for(ll bitpos = 0ll; bitpos < 5ll; bitpos++) {
                if((tickets >> bitpos) & 0b1) {
                    out_adj[(u << num_tickets) | tickets].push_back({(v << num_tickets) | (tickets ^ (1ll << bitpos)), (c / 10ll) * (10ll - bitpos - 1ll)});
                    in_adj[(v << num_tickets) | (tickets ^ (1ll << bitpos))].push_back({(u << num_tickets) | tickets, (c / 10ll) * (10ll - bitpos - 1ll)});
                }
            }
        }
    }

    // Dijkstra from the cities
    vector<ll> dist(n * ticket_combs, -1ll);
    priority_queue<pll, vector<pll>, greater<pll>> pq;
    
    for(ll v_city : v_cities) {
        pq.push({0ll, v_city});
    }

    while(!pq.empty()) {
        ll curd, curn;
        tie(curd, curn) = pq.top();
        pq.pop();

        if(dist[curn] != -1ll) continue;
        dist[curn] = curd;

        for(pll e : in_adj[curn]) {
            pq.push({curd + e.second, e.first});
        }
    }

    // for(ll i = 0ll; i < n * ticket_combs; i++) {
    //     std::cout << "DEBUG: dist[" << i << "] = " << dist[i] << endl;
    // }

    ll q;
    cin >> q;

    while(q--) {
        ll s;
        vector<ll> p(5ll, 0ll);
        cin >> s >> p[0] >> p[1] >> p[2] >> p[3] >> p[4];

        ll ans = numeric_limits<ll>::max();

        for(ll i = 0ll; i < ticket_combs; i++) {
            bool valid = true;
            ll total_ticket_price = 0ll;
            for(ll bitpos = 0ll; bitpos < num_tickets; bitpos++) {
                if(((i >> bitpos) & 1ll)) {
                    ll ticket_price = p[bitpos];
                    if(ticket_price == -1ll) {
                        valid = false;
                        break;
                    }
                    total_ticket_price += ticket_price;
                }
            }

            if(valid) {
                ans = min(ans, total_ticket_price + dist[(s << num_tickets) | i]);
            }
        }

        std::cout << ans << endl;
    }

    return 0;
}

• 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