oj.uz

Submission #674969

# Submission time Handle Problem Language Result Execution time Memory
674969 2022-12-26T17:50:38 Z flashhh Cities (BOI16_cities) C++17
100 / 100
 1951 ms 45000 KB 
#include <bits/stdc++.h>
#define getbit(x,y) (((x)>>(y))&1)
#define getoff(x,y) ((x)^(1<<(y)))
#define bp __builtin_popcount

using namespace std;

int numVertices, numEdges, numImportantVertices;
vector<int> importantVertices;
vector<vector<long long> > dp;
vector<vector<pair<int,int> > > adj;

void init() {
    //freopen(".inp","r",stdin);
    //freopen(".out","w",stdout);
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
}

void Read() {
    cin >> numVertices >> numImportantVertices >> numEdges;

    importantVertices.resize(numImportantVertices);
    adj.resize(numVertices);

    for (int numImportantVertice = 0; numImportantVertice < numImportantVertices; ++numImportantVertice) {
        cin >> importantVertices[numImportantVertice];
        --importantVertices[numImportantVertice];
    }

    for (int edge = 0; edge < numEdges; ++edge) {
        int u,v,w; cin >> u >> v >> w;
        --u; --v;
        
        adj[u].emplace_back(w, v);
        adj[v].emplace_back(w, u);
    }
}

void calculate() {
    auto modifyMin = [&] (long long &x, long long y) {
        if (x > y) x = y;
    };

    dp.resize(1 << numImportantVertices);
    for (int maskOfImportantVertice = 0; maskOfImportantVertice < (1 << numImportantVertices); ++maskOfImportantVertice)
        dp[maskOfImportantVertice].resize(numVertices, (long long) 1e18);
    
    for (int numImportantVertice = 0; numImportantVertice < numImportantVertices; ++numImportantVertice) {
        int gatherVertice = importantVertices[numImportantVertice];
        dp[1<<numImportantVertice][gatherVertice] = 0;
    }

    for (int maskOfImportantVertice = 1; maskOfImportantVertice < (1 << numImportantVertices); ++maskOfImportantVertice) {
        if (bp(maskOfImportantVertice) > 1) {
            for (int gatherVertice = 0; gatherVertice < numVertices; ++gatherVertice) {
                for (int subMaskOfImportantVertice = maskOfImportantVertice; subMaskOfImportantVertice > 0; subMaskOfImportantVertice = (subMaskOfImportantVertice-1) & maskOfImportantVertice) {
                    int remainMaskOfImportantVertice = maskOfImportantVertice ^ subMaskOfImportantVertice;
                    if (remainMaskOfImportantVertice == 0) continue;

                    modifyMin(dp[maskOfImportantVertice][gatherVertice], dp[subMaskOfImportantVertice][gatherVertice] + dp[remainMaskOfImportantVertice][gatherVertice]);
                }
            }
        }

        priority_queue<pair<long long,int>, vector<pair<long long,int> >, greater<pair<long long,int> > > myPrioQueue;
        for (int gatherVertice = 0; gatherVertice < numVertices; ++gatherVertice) myPrioQueue.emplace(dp[maskOfImportantVertice][gatherVertice], gatherVertice);

        while (!myPrioQueue.empty()) {
            auto [distance, gatherVertice] = myPrioQueue.top(); myPrioQueue.pop();
            if (dp[maskOfImportantVertice][gatherVertice] != distance) continue;

            for (auto [weight, newGatherVertice]:adj[gatherVertice])
                if (dp[maskOfImportantVertice][newGatherVertice] > distance + weight) {
                    dp[maskOfImportantVertice][newGatherVertice] = distance + weight;
                    myPrioQueue.emplace(dp[maskOfImportantVertice][newGatherVertice], newGatherVertice);
                }
        }
    }
}

void printAnswer() {
    auto modifyMin = [&] (long long &x, long long y) {
        if (x > y) x = y;
    };

    long long result = (long long) 1e18;
    for (int gatherVertice = 0; gatherVertice < numVertices; ++gatherVertice)
        modifyMin(result, dp[(1<<numImportantVertices)-1][gatherVertice]);
    
    cout << result <<'\n';
}

int main() {
    init();
    Read();

    calculate();

    printAnswer();
    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 0 ms 320 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 324 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 510 ms 25988 KB Output is correct
2 Correct 499 ms 26028 KB Output is correct
3 Correct 307 ms 17816 KB Output is correct
4 Correct 58 ms 8556 KB Output is correct
5 Correct 261 ms 22748 KB Output is correct
6 Correct 54 ms 8492 KB Output is correct
7 Correct 3 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 596 KB Output is correct
2 Correct 5 ms 596 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 3 ms 464 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1004 ms 32292 KB Output is correct
2 Correct 905 ms 32384 KB Output is correct
3 Correct 628 ms 24112 KB Output is correct
4 Correct 511 ms 21296 KB Output is correct
5 Correct 141 ms 11988 KB Output is correct
6 Correct 64 ms 10184 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1938 ms 45000 KB Output is correct
2 Correct 1951 ms 44832 KB Output is correct
3 Correct 1840 ms 44872 KB Output is correct
4 Correct 1280 ms 36796 KB Output is correct
5 Correct 1008 ms 27660 KB Output is correct
6 Correct 216 ms 13248 KB Output is correct
7 Correct 71 ms 10244 KB Output is correct