Submission #896369

#	Time	Username	Problem	Language	Result	Execution time	Memory
896369		PenguinsAreCute	Voting Cities (NOI22_votingcity)	C++17	100 / 100	129 ms	38404 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define LL_MAX LONG_LONG_MAX
#define LL_MIN LONG_LONG_MIN
#define speed ios_base::sync_with_stdio(false); cin.tie(0)
#define stMx(a,b) a = max(a,b)
#define stMn(a,b) a = min(a,b)
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef set<int> si;
typedef vector<ii> vii;
typedef set<ii> sii;
#define REP(i, a, b) for(int i = a; i < b; i++)
#define HASTC 0
vii adj[161210];
priority_queue<ii, vector<ii>, greater<ii> > pq;
int dist[161210], best[161210];
#define MP(a, b) make_pair(a, b)
void dijkstra(int source) {
    pq.push(ii(0, source)); dist[source] = 0;
    while(!pq.empty()){
        ii c = pq.top(); pq.pop();
        int x = c.second, d = c.first;
        if(d != dist[x]) continue; 
        for(auto i : adj[x]){
            if(dist[i.first] > d + i.second){
                best[i.first]=x;
                dist[i.first] = d + i.second;
                pq.push(ii(dist[i.first], i.first));
            }
        }
    }
}
void solvetc(int idx) {
    int N, E, K, T, U, V, C, Q, S, P[5]; cin >> N >> E >> K;
    REP(i,0,K) {
        cin>>T;
        adj[161209].pb(ii(T<<5,0));
    }
    REP(i,0,E) {
        cin>>U>>V>>C;
        REP(j,0,32) {
            adj[(V<<5)+j].pb(ii((U<<5)+j,C));
            REP(k,0,5) if(!(j&(1<<k))) adj[(V<<5)+j].pb(ii((U<<5)+j+(1<<k),C/10*(9-k)));
        }
    }
    cin>>Q;
    REP(i,0,161210) dist[i]=6942012102010;
    dijkstra(161209);
    while(Q--) {
        cin>>S; REP(i,0,5)cin>>P[i];
        int min_dist=6942012102010;
        REP(i,0,32) {
            int cur_dist=dist[(S<<5)+i];
            REP(j,0,5) if(i&(1<<j)) cur_dist+=(P[j]==-1?6942012102010:P[j]);
            min_dist=min(min_dist,cur_dist);
        }
        cout<<(min_dist==6942012102010?-1:min_dist)<<"\n";
    }
}
int32_t main() {
    int tc;
    if(HASTC) cin>>tc;
    else tc=1;
    for(int i=0;i<tc;i++) solvetc(i);    
}

• 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