oj.uz

Submission #1073218

# Submission time Handle Problem Language Result Execution time Memory
1073218 2024-08-24T10:37:03 Z Jarif_Rahman Cities (BOI16_cities) C++17
100 / 100
 1381 ms 48424 KB 
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

const ll inf = 1e18;
const int N = 1e5;

bitset<N> bl;
void dijkstra(int n, vector<pair<int, ll>> *graph, ll* dis){
    bl.reset();
    priority_queue<pair<ll, int>> pq;
    for(int s = 0; s < n; s++) if(dis[s] < inf) pq.push({-dis[s], s});
    
    while(!pq.empty()){
        int nd = pq.top().second;
        pq.pop();
        if(bl[nd]) continue;
        bl[nd] = 1;
        for(auto [x, w]: graph[nd]) if(dis[nd]+w < dis[x]){
            dis[x] = dis[nd]+w;
            pq.push({-dis[x], x});
        }
    }
}

int n, m, k;
vector<pair<int, ll>> graph[N];
vector<int> ic;
ll dis[32][N];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> k >> m;

    ic.resize(k);
    for(int &x: ic) cin >> x, x--;

    for(int i = 0; i < m; i++){
        int a, b; ll w; cin >> a >> b >> w; a--, b--;
        graph[a].push_back({b, w});
        graph[b].push_back({a, w});
    }

    for(int i = 0; i < k; i++){
        fill(dis[1<<i], dis[1<<i]+n, inf);
        dis[1<<i][ic[i]] = 0;
        dijkstra(n, graph, dis[1<<i]);
    }

    for(int mask = 1; mask < (1<<k); mask++){
        if(__builtin_popcount(mask) < 2) continue;
        fill(dis[mask], dis[mask]+n, inf);
        for(int submask = (mask-1)&mask; submask > 0; submask = (submask-1)&mask){
            for(int i = 0; i < n; i++)
                dis[mask][i] = min(dis[mask][i], dis[submask][i]+dis[mask^submask][i]);
        }
        dijkstra(n, graph, dis[mask]);
    }

    cout << *min_element(dis[(1<<k)-1], dis[(1<<k)-1]+n) << "\n";
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 3000 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 1 ms 2908 KB Output is correct
5 Correct 1 ms 3164 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 29892 KB Output is correct
2 Correct 279 ms 29376 KB Output is correct
3 Correct 154 ms 20108 KB Output is correct
4 Correct 43 ms 17600 KB Output is correct
5 Correct 158 ms 24840 KB Output is correct
6 Correct 43 ms 17500 KB Output is correct
7 Correct 3 ms 5212 KB Output is correct
8 Correct 2 ms 3164 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3416 KB Output is correct
2 Correct 5 ms 3420 KB Output is correct
3 Correct 3 ms 3164 KB Output is correct
4 Correct 3 ms 3164 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 671 ms 36108 KB Output is correct
2 Correct 658 ms 35576 KB Output is correct
3 Correct 407 ms 26336 KB Output is correct
4 Correct 372 ms 28172 KB Output is correct
5 Correct 111 ms 19496 KB Output is correct
6 Correct 56 ms 19796 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1381 ms 48408 KB Output is correct
2 Correct 1358 ms 48424 KB Output is correct
3 Correct 1328 ms 47972 KB Output is correct
4 Correct 842 ms 38456 KB Output is correct
5 Correct 748 ms 34576 KB Output is correct
6 Correct 182 ms 20900 KB Output is correct
7 Correct 58 ms 20180 KB Output is correct