oj.uz

Submission #557098

# Submission time Handle Problem Language Result Execution time Memory
557098 2022-05-04T17:58:44 Z OttoTheDino Cities (BOI16_cities) C++17
74 / 100
 6000 ms 119888 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 = 3;

    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 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 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 1481 ms 44608 KB Output is correct
2 Correct 1444 ms 44316 KB Output is correct
3 Correct 1064 ms 36756 KB Output is correct
4 Correct 154 ms 9596 KB Output is correct
5 Correct 739 ms 32152 KB Output is correct
6 Correct 84 ms 9424 KB Output is correct
7 Correct 7 ms 744 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 1012 KB Output is correct
2 Correct 13 ms 980 KB Output is correct
3 Correct 9 ms 940 KB Output is correct
4 Correct 12 ms 724 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3258 ms 69820 KB Output is correct
2 Correct 2896 ms 69436 KB Output is correct
3 Correct 2365 ms 61832 KB Output is correct
4 Correct 1833 ms 40772 KB Output is correct
5 Correct 610 ms 16096 KB Output is correct
6 Correct 417 ms 11944 KB Output is correct

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6047 ms 119888 KB Time limit exceeded
2 Halted 0 ms 0 KB -