Submission #1169811

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169811		Thanhs	Voting Cities (NOI22_votingcity)	C++20	100 / 100	64 ms	8436 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define name "TENBAI"
#define fi first
#define se second
#define int long long
#define endl '\n'
#define setmin(x, y) x = min((x), (y))
#define setmax(x, y) x = max((x), (y))
#define sqr(x) ((x) * (x))

mt19937 hdp(chrono::high_resolution_clock::now().time_since_epoch().count());
int rand(int l, int r){return l + ((hdp() % (r - l + 1)) + r - l + 1) % (r - l + 1);}

const int NM = 5e3 + 5;
const int EM = 32 + 5;

vector<pair<int, int>> g[NM];
int n, m, p[5], d[NM][EM], k;
priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<>> pq;

void solve()
{
    memset(d, 0x3f, sizeof d);
    cin >> n >> m >> k;
    for (int i = 1; i <= k; i++)
    {
        int x;
        cin >> x;
        d[x][0] = 0;
        pq.push({0, {x, 0}});
    }
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        g[v].emplace_back(u, w);
    }
    while (!pq.empty())
    {
        pair<int, int> u = pq.top().se;
        int w = pq.top().fi;
        pq.pop();
        if (d[u.fi][u.se] != w)
            continue;
        for (auto v : g[u.fi])
            for (int i = -1; i < 5; i++)
                if (i == -1 || u.se >> i & 1 ^ 1)
                {
                    int nmsk = u.se | (i == -1 ? 0 : 1 << i);
                    if (d[v.fi][nmsk] > w + v.se / 10 * (9 - i))
                    {
                        d[v.fi][nmsk] = w + v.se / 10 * (9 - i);
                        pq.push({d[v.fi][nmsk], {v.fi, nmsk}});
                    }
                }
    }
    int q;
    cin >> q;
    while (q--)
    {
        int s, msk = 0;
        cin >> s;
        for (int i = 0; i < 5; i++)
        {
            cin >> p[i];
            if (p[i] != -1)
                msk |= 1 << i;
        }
        int res = d[0][32];
        for (int smsk = msk; ;smsk = (smsk - 1) & msk)
        {
            int t = d[s][smsk];
            for (int i = 0; i < 5; i++)
                if (smsk >> i & 1)
                    t += p[i];
            setmin(res, t);
            if (!smsk)
                break;
        }
        cout << (res >= 1e18 ? -1 : res) << endl;
    }
}

signed main()
{
    if (fopen("in.txt", "r")) 
    {
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    }
    else if (fopen(name".inp", "r"))
    {
        freopen(name".inp", "r", stdin);
        freopen(name".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int tc = 1; 
    // cin >> tc;
    while (tc--)
        solve();
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:90:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |         freopen("in.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:91:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |         freopen("out.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:95:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |         freopen(name".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:96:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |         freopen(name".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• 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