oj.uz

Submission #557099

# Submission time Handle Problem Language Result Execution time Memory
557099 2022-05-04T18:00:06 Z OttoTheDino Cities (BOI16_cities) C++17
100 / 100
 5059 ms 99080 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

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

#define rep(i,s,e)                  for (ll i = s; i <= e; ++i)
#define rrep(i,s,e)                 for (ll i = s; i >= e; --i)
#define pb                          push_back
#define pf                          push_front
#define fi                          first
#define se                          second
#define all(a)                      a.begin(), a.end()
#define len(a)                      (ll)a.size()
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ii> vii;
typedef vector<ll> vi;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;

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

    ll n, k, m; cin >> n >> k >> m;
    
    ll T = 2;

    ll dp[T+1][n][1<<k] = {};

    vii adj[n];

    rep (i,0,n-1) rep (j,1,(1<<k)-1) dp[0][i][j] = 1e15;

    rep (i,0,k-1) {
        ll x; cin >> x;
        --x;
        dp[0][x][1<<i] = 0;
    }

    rep (i,0,m-1) {
        ll u, v, c; cin >> u >> v >> c;
        u--, v--;
        adj[u].pb({v, c});
        adj[v].pb({u, c});
    }

    rep (a,0,T-1) {

        rep (i,0,(1<<k)-1) {

            priority_queue<ii, vii, greater<ii>> pq;

            bool done[n] = {};

            rep (j,0,n-1) pq.push({dp[a][j][i], j});

            while (!pq.empty()) {
                ll u = pq.top().se, D = pq.top().fi;
                pq.pop();

                if (done[u]) continue;
                done[u] = 1;

                for (auto vc : adj[u]) {
                    if (D + vc.se < dp[a][vc.fi][i]) {
                        dp[a][vc.fi][i] = D + vc.se;
                        pq.push({dp[a][vc.fi][i], vc.fi});
                    }
                }
            }

        }

        //join together different trees
        rep (i,0,n-1) {
            rep (j,0,(1<<k)-1) dp[a+1][i][j] = dp[a][i][j];

            for (auto vc : adj[i])
                rrep (j,(1<<k)-1,0)
                    rep (b,0,(1<<k)-1)
                        if ((j&b)==b)
                            dp[a+1][i][j] = min(dp[a+1][i][j], dp[a+1][i][j^b]+vc.se+dp[a][vc.fi][b]);
        }
    }

    ll ans = LLONG_MAX;
    rep (i,0,n-1) ans = min(ans, dp[T][i][(1<<k)-1]);
    cout << ans << "\n";

    return 0;
}

Subtask #1
22.0 / 22.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1082 ms 38400 KB Output is correct
2 Correct 1022 ms 37980 KB Output is correct
3 Correct 773 ms 30412 KB Output is correct
4 Correct 124 ms 9584 KB Output is correct
5 Correct 579 ms 29080 KB Output is correct
6 Correct 81 ms 9464 KB Output is correct
7 Correct 4 ms 596 KB Output is correct
8 Correct 3 ms 596 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 840 KB Output is correct
2 Correct 10 ms 852 KB Output is correct
3 Correct 6 ms 724 KB Output is correct
4 Correct 9 ms 676 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2197 ms 57216 KB Output is correct
2 Correct 2121 ms 56816 KB Output is correct
3 Correct 1508 ms 49248 KB Output is correct
4 Correct 1272 ms 34496 KB Output is correct
5 Correct 440 ms 14816 KB Output is correct
6 Correct 340 ms 11880 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4761 ms 94788 KB Output is correct
2 Correct 4720 ms 99080 KB Output is correct
3 Correct 5059 ms 98528 KB Output is correct
4 Correct 3178 ms 88900 KB Output is correct
5 Correct 2934 ms 57496 KB Output is correct
6 Correct 1426 ms 22392 KB Output is correct
7 Correct 1094 ms 15804 KB Output is correct