oj.uz

Submission #557093

# Submission time Handle Problem Language Result Execution time Memory
557093 2022-05-04T17:49:32 Z OttoTheDino Cities (BOI16_cities) C++17
74 / 100
 6000 ms 126884 KB 
#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) {

            set<ii> st;

            bool done[n] = {};

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

            while (!st.empty()) {
                auto el = *st.begin();
                st.erase(st.begin());
                ll u = el.se, D = el.fi;

                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;
                        st.insert({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 320 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 340 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2567 ms 51656 KB Output is correct
2 Correct 2250 ms 52708 KB Output is correct
3 Correct 1540 ms 41316 KB Output is correct
4 Correct 184 ms 12888 KB Output is correct
5 Correct 1144 ms 39212 KB Output is correct
6 Correct 102 ms 12720 KB Output is correct
7 Correct 8 ms 784 KB Output is correct
8 Correct 4 ms 592 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 980 KB Output is correct
2 Correct 17 ms 980 KB Output is correct
3 Correct 12 ms 972 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 5710 ms 76812 KB Output is correct
2 Correct 5203 ms 77748 KB Output is correct
3 Correct 3075 ms 66424 KB Output is correct
4 Correct 2977 ms 46868 KB Output is correct
5 Correct 814 ms 20460 KB Output is correct
6 Correct 509 ms 15208 KB Output is correct

Subtask #5
0 / 26.0

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