Submission #1125720

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125720		CodeLakVN	Voting Cities (NOI22_votingcity)	C++20	100 / 100	200 ms	8672 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 EDGE {
    int u, v, w;
} edges[2 * 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";
        }
    }
}

namespace sub8 {
    // + build a new directed graph that contain all nodes of the base graph and reverse all edges of the base graph
    // + create a new super source (n + 1) that has edges to special nodes with w = 0
    // + then run dijkstra as subtask 7 from the super source to other nodes
    // + then for each query, we just need to consider the shortest path from the super source to s, because if we want to reach s, we must pass through one of the special nodes, because the super source only has edge from it to special nodes
    
    vector<ii> newADJ[N];

    void buildADJ() {
        FOR(i, 1, numEdge) {
            int u = edges[i].u, v = edges[i].v, w = edges[i].w;
            newADJ[v].push_back({u, w});
        }
        int newNode = numNode + 1;
        FOR(i, 1, numSpec) newADJ[newNode].push_back({specNode[i], 0});
    }

    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;
        }
    };

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

    ll dist[N][33];

    void dijkstra(int s) {
        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 : newADJ[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)) {
                    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() {
        buildADJ();
        dijkstra(numNode + 1);
        FOR(t, 1, numQuery) {
            int s = query[t].s;
            ll ans = dist[0][0];
            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[s][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++;
        edges[i] = {u, v, w};
        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 if (numEdge <= 1000 && numNode <= 100) sub7::solve();
    else sub8::solve();

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

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:235:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  235 |         freopen(Task".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:236:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  236 |         freopen(Task".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