Submission #1125711

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125711		CodeLakVN	Voting Cities (NOI22_votingcity)	C++20	30 / 100	201 ms	1252 KiB

Main

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

#define Task "VOTINGCITY"
#define ll long long
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FOD(i, a, b) for (int i = (a); i >= (b); i--)
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define F first
#define S second

typedef pair<int, int> ii;
typedef pair<ll, int> li;

const int N = 5e3 + 5;
const ll INF = 1e18;
const int MOD = 1e9 + 7;

template<class X, class Y>
    bool minimize(X &x, Y y) {
        if (x > y) {
            x = y;
            return true;
        } else return false;
    }

int numNode, numEdge, numQuery, numSpec;
int specNode[N];
vector<ii> adj[N];

struct QUERY {
    int s;
    int price[6];
} query[105];

ll dist[N];

void dijkstra(int s) {
    priority_queue<li, vector<li>, greater<li>> pq;
    pq.push({0, s});
    memset(dist, 0x3f, sizeof(dist));
    dist[s] = 0;
    while (!pq.empty()) {
        li p = pq.top();
        pq.pop();
        int u = p.S;
        ll d = p.F;
        if (d > dist[u]) continue;
        for (ii e : adj[u]) {
            int v = e.F, w = e.S;
            if (minimize(dist[v], dist[u] + w)) 
                pq.push({dist[v], v});
        }
    }
}

namespace sub3 {
    bool valid() {
        FOR(i, 1, numQuery) if (*max_element(query[i].price + 1, query[i].price + 6) > -1)
            return false;
        return true;
    }

    void solve() {
        FOR(i, 1, numQuery) {
            int s = query[i].s;
            dijkstra(s);
            ll ans = dist[0];
            FOR(j, 1, numSpec) minimize(ans, dist[specNode[j]]);
            cout << (ans == dist[0] ? -1 : ans) << "\n";
        }
    }
}

namespace sub7 {
    // + iterate over possible groups of tickets that are bought
    // + run dijkstra from s with 3 states {dist, u, bitmask (the ith bit is on if the ticket i was bought)}
    // + iterate over special nodes to minimize the answer

    bool isValidMask(int mask, int queryID) {
        FOR(i, 0, 4) if (mask >> i & 1) {
            if (query[queryID].price[i + 1] == -1) return false;
        }
        return true;
    }

    struct STATE {
        int u;
        long long dist;
        int mask;

        bool operator < (const STATE &other) const {
            return dist > other.dist;
        }
    };

    ll dist[105][33];

    void printMask(int mask) {
        FOR(i, 0, 4) cout << (mask >> i & 1);
    }

    void dijkstra(int s, int queryID) {
        priority_queue<STATE> pq;
        pq.push({s, 0, 0});
        memset(dist, 0x3f, sizeof(dist));
        dist[s][0] = 0;
        while (!pq.empty()) {
            STATE t = pq.top();
            pq.pop();
            int u = t.u, preMask = t.mask;
            long long d = t.dist;
            if (d > dist[u][preMask]) continue;
            // cout << u << ": dist: " << d << ", mask: ";
            // printMask(preMask);
            // cout << "\n";
            for (ii e : adj[u]) {
                int v = e.F, w = e.S;
                if (minimize(dist[v][preMask], dist[u][preMask] + 1LL * w))
                    pq.push({v, dist[v][preMask], preMask});
                FOR(i, 0, 4) if (!(preMask >> i & 1) && (query[queryID].price[i + 1] != -1)) {
                    int newMask = (preMask | (1 << i));
                    if (minimize(dist[v][newMask], dist[u][preMask] + 1LL * w - 1LL * w * (i + 1) / 10))
                        pq.push({v, dist[v][newMask], newMask});
                }
            }
        }
    }   

    void solve() {
        FOR(t, 1, numQuery) {
            dijkstra(query[t].s, t);
            ll ans = dist[0][0];
            FOR(i, 1, numSpec) FOR(mask, 0, (1 << 5) - 1) if (isValidMask(mask, t)) {
                ll ticketCost = 0;
                FOR(k, 0, 4) if (mask >> k & 1) ticketCost += query[t].price[k + 1];
                minimize(ans, dist[specNode[i]][mask] + ticketCost);
            }
            cout << (ans == dist[0][0] ? -1 : ans) << "\n";
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if (fopen(Task".INP", "r")) {
        freopen(Task".INP", "r", stdin);
        freopen(Task".OUT", "w", stdout);
    }
    
    cin >> numNode >> numEdge >> numSpec;
    FOR(i, 1, numSpec) cin >> specNode[i], specNode[i]++;
    FOR(i, 1, numEdge) {
        int u, v, w;
        cin >> u >> v >> w;
        u++;
        v++;
        adj[u].push_back({v, w});
    }
    cin >> numQuery;
    FOR(i, 1, numQuery) {
        cin >> query[i].s;
        query[i].s++;
        FOR(j, 1, 5) cin >> query[i].price[j];
    }
    
    if (sub3::valid()) sub3::solve();
    else sub7::solve();

    cerr << TIME << "s\n";

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:148:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  148 |         freopen(Task".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:149:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  149 |         freopen(Task".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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