Submission #1151071

#	Time	Username	Problem	Language	Result	Execution time	Memory
1151071		vicvic	Voting Cities (NOI22_votingcity)	C++20	100 / 100	103 ms	12276 KiB

Main

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <cstdint>
#include <queue>
#define int long long
using namespace std;
const int inf=1e16;
int n, e, k;
vector <pair <int, int>> vec[5005];
int voting[5005], price[10], dp[5005][(1 << 5)];
priority_queue <vector <int>, vector <vector <int>>, greater <vector <int>>> setul;
vector <int> v;
struct query
{
    int nod, poz, rez;
    int price[10];
    query ()
    {

    }
    query (int nod, int *v, int poz)
    {
        this -> nod=nod;
        for (int i=0;i<=4;i++)
        {
            this -> price[i]=v[i];
        }
        this -> poz=poz;
    }
} q[1005];
void dijkstra ()
{
    for (int i=0;i<=n;i++)
    {
        for (int j=0;j<(1 << 5);j++)
        {
            dp[i][j]=inf;
        }
    }
    /// pret, nod, stare
    for (auto nod : v)
    {
        for (int j=0;j<(1 << 5);j++)
        {
            dp[nod][j] = 0;
            setul.push({0, nod, j});
        }
    }
    while (!setul.empty())
    {
        auto chestie=setul.top();
        setul.pop();
        if (chestie[0]!=dp[chestie[1]][chestie[2]])
            continue;
        for (auto adj : vec[chestie[1]])
        {
            if (dp[adj.first][chestie[2]]>dp[chestie[1]][chestie[2]]+adj.second)
            {
                dp[adj.first][chestie[2]]=dp[chestie[1]][chestie[2]]+adj.second;
                setul.push ({dp[adj.first][chestie[2]], adj.first, chestie[2]});
            }
            for (int j=0;j<=4;j++)
            {
                int stare=chestie[2];
                if (!(stare & (1 << j)))
                {
                    int stare2=stare | (1 << j);
                    if (dp[adj.first][stare2]>dp[chestie[1]][chestie[2]]+adj.second-adj.second*(j+1)/10)
                    {
                        dp[adj.first][stare2]=dp[chestie[1]][chestie[2]]+adj.second-adj.second*(j+1)/10;
                        setul.push ({dp[adj.first][stare2], adj.first, stare2});
                    }
                }
            }
        }
    }
}
int32_t main ()
{
    ios :: sync_with_stdio (0);
    cin.tie (nullptr);
    cin >> n >> e >> k;
    for (int i=1;i<=k;i++)
    {
        int x;
        cin >> x;
        voting[x]=1;
        v.push_back (x);
    }
    for (int i=1;i<=e;i++)
    {
        int x, y, c;
        cin >> x >> y >> c;
        vec[y].push_back ({x, c});
    }
    int nrq;
    cin >> nrq;
    for (int i=1;i<=nrq;i++)
    {
        int x;
        cin >> x;
        for (int i=0;i<=4;i++)
        {
            cin >> price[i];
        }
        q[i]=query (x, price, i);
    }
    dijkstra ();
    sort (q+1, q+nrq+1, [] (query a, query b) {return a.nod<b.nod;});
    int crt=-1;
    for (int i=1;i<=nrq;i++)
    {
        int mn = inf;
        for (int msk = 0; msk < (1 << 5); msk++)
        {
            bool ok = 1;
            int t_price = 0;
            for (int j = 0; j <= 4; j++)
            {
                if ((msk & (1 << j)) && q[i].price[j] == -1)
                {
                    ok = 0;
                }
                if ((msk & (1 << j)))
                {
                    t_price += q[i].price[j];
                }
            }
            if (!ok)
                continue;
            mn=min (mn, dp[q[i].nod][msk]+t_price);
        }
        q[i].rez=(mn>=inf?-1:mn);
    }
    sort (q+1, q+nrq+1, [] (query a, query b) {return a.poz<b.poz;});
    for (int i=1;i<=nrq;i++)
    {
        cout << q[i].rez << "\n";
    }
    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