Submission #787072

#	Time	Username	Problem	Language	Result	Execution time	Memory
787072		Ozy	Voting Cities (NOI22_votingcity)	C++17	45 / 100	1072 ms	8356 KiB

Main

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define repa(i,a,b) for(int i = (a); i >= (b); i--)
#define pll pair<lli,lli>

#define MAX 5000
//para la cola
#define v first
#define pos second.first
#define usados second.second
//para los hijos
#define des first
#define w second

lli n,k,m,a,b,c,res,q,s;
lli votantes[MAX+2],dp[MAX+2][(1<<5)],costos[5];
vector<pll> hijos[MAX+2];
priority_queue<pair<lli,pll> > cola;
pair<lli,pll> act;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m >> k;
    rep(i,1,k) {
        cin >> a;
        votantes[a] = 1;
    }
    rep(i,1,m) {
        cin >> a >> b >> c;
        hijos[a].push_back({b,c});
    }

    cin >> q;
    rep(Q,1,q) {

        //limpia
        rep(i,0,n-1) {
            rep(j,0,(1<<5)-1) {
                dp[i][j] = 0;
            }
        }
        while (!cola.empty()) cola.pop();

        cin >> s;
        rep(i,0,4) cin >> costos[i];

        res = 0;
        cola.push({-1,{s,0}});
        while (!cola.empty()) {

            act = cola.top();
            cola.pop();
            act.v *= -1;

            if (dp[act.pos][act.usados] != 0) continue;
            dp[act.pos][act.usados] = act.v;

            if (votantes[act.pos] == 1) {
                res = act.v;
                break;
            }

            //busaco usando alguno de mis hijos
            rep(pot,0,4) {
                if (act.usados & (1<<pot) || costos[pot] == -1) continue;
                for(auto h : hijos[act.pos]) {
                    if (dp[h.des][act.usados+(1<<pot)] != 0) continue;
                    a = h.w/10;
                    a *= 9 - pot;
                    a += costos[pot];
                    cola.push({-(act.v + a),{h.des,act.usados+(1<<pot)}});
                }
            }
            for(auto h : hijos[act.pos]) {
                if (dp[h.des][act.usados] != 0) continue;
                cola.push({-(act.v + h.w),{h.des,act.usados}});
            }

        }

        res--;
        cout << res << "\n";
    }

    //restar uno siempre a res ya que se lo sumo al principio

    return 0;
}

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