Submission #1272192

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272192		thesen	Voting Cities (NOI22_votingcity)	C++20	100 / 100	155 ms	14660 KiB

Main

#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define vll vector <ll>
#define vbool vector<bool>
#define pairll pair<ll,ll>
#define fi first
#define sc second
#define rever greater<ll>()
using namespace std;

struct dta{
    ll w, i, x;
    bool operator<(const dta &a)const{
        return w > a.w;
    }
};

void solve(){
    ll n, m, k; cin >> n >> m >> k;
    vll t(k); for(ll i = 0; i < k; i++) cin >> t[i];

    vector<vll> path(n), c(n);
    for(ll i = 0, u, v, wei; i < m; i++){
        cin >> u >> v >> wei;
        path[v].pb(u); c[v].pb(wei);
    }

    vll pw(15); 
    pw[0] = 1; for(ll i = 1; i < 15; i++)pw[i] = pw[i-1]*2;

    priority_queue<dta> pq;
    for(ll i = 0; i < k; i++){
        pq.push({0, t[i], 0});
    }
    vector<vll> res(n, vll(32, 1e18));
    ll i, w, x;
    while(pq.size()){
        i = pq.top().i; w = pq.top().w; x = pq.top().x;
        pq.pop();

        if(res[i][x] < 1e18)continue;
        res[i][x] = w;

        for(ll j = 0; j < path[i].size(); j++){
            if(res[path[i][j]][x] < 1e18)continue;
            pq.push({w+c[i][j], path[i][j], x});
        }
        for(ll p = 0; p < 5; p++){
            if(x%pw[p+1] >= pw[p])continue;
            for(ll j = 0; j < path[i].size(); j++){
                if(res[path[i][j]][x+pw[p]] < 1e18)continue;
                pq.push({w+c[i][j]/10*(9-p), path[i][j], x+pw[p]});
                //cout << w+c[i][j]/10*(9-p) << ' ' << path[i][j] << x+pw[p] << endl;
            }
        }
    }

    // for(ll j = 0; j < 32; j++){
    //     if(res[1][j] == 1e18)continue;
    //     cout << j << ' ' << res[1][j] << endl;
    // }cout << endl;
    // for(ll j = 0; j < 32; j++){
    //     if(res[0][j] == 1e18)continue;
    //     cout << j << ' ' << res[0][j] << endl;
    // }cout << endl;

    ll q; cin >> q;
    ll s, ans, tot; vll p(5);
    while(q--){
        cin >> s; for(ll j = 0; j < 5; j++)cin >> p[j];

        ans = 1e18;
        for(ll y = 0; y < 32; y++){
            if(res[s][y] == 1e18)continue;
            //cout << s << ' ' << y << ' ' << res[s][y] << endl;
            
            x = y; tot = res[s][y];
            if(x >= pw[4]){
                x -= pw[4];
                if(p[4] == -1)continue;
                tot += p[4]; 
                //cout << 4;
            }
            if(x >= pw[3]){
                x -= pw[3];
                if(p[3] == -1)continue;
                tot += p[3]; 
                //cout << 3;
            }
            if(x >= pw[2]){
                x -= pw[2];
                if(p[2] == -1)continue;
                tot += p[2]; 
                //cout << 2;
            }
            if(x >= pw[1]){
                x -= pw[1];
                if(p[1] == -1)continue;
                tot += p[1]; 
                //cout << 1;
            }
            if(x >= pw[0]){
                x -= pw[0];
                if(p[0] == -1)continue;
                tot += p[0]; 
                //cout << 0;
            }//cout<< endl;
            //cout << tot << ' ' << y << ' ' << res[s][y] << endl;
            ans = min(ans, tot);
        }
        if(ans == 1e18)cout << -1 << endl;
        else cout << ans << endl;
    }
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    ll t=1; //cin >> t;
    for(int i = 1; i <= t; i++){
        solve();
    }
}

• 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