oj.uz

Submission #485517

# Submission time Handle Problem Language Result Execution time Memory
485517 2021-11-08T03:31:33 Z generic_placeholder_name Cities (BOI16_cities) C++17
100 / 100
 1906 ms 39688 KB 
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")
#pragma GCC target("avx,avx2,fma")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#include <ext/rope>

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define gcd __gcd
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define rep(i, n) for (int i=0; i<(n); i++)
#define rep1(i, n) for (int i=1; i<=(n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define endl "\n"

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned uint;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
template<typename T, typename cmp = less<T>>
using ordered_set=tree<T, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
typedef trie<string, null_type, trie_string_access_traits<>, pat_trie_tag, trie_prefix_search_node_update> pref_trie;

constexpr int N = 1e5 + 5;
constexpr int K = 5;
constexpr ll INF = 1e18;

vector<pii> adj[N];
int v[K];
ll dist[1 << K][N];
ll dp[1 << K];

int32_t main() {
    fastio;
    int n, k, m; cin >> n >> k >> m;
    rep(i, k) cin >> v[i], --v[i];
    rep(i, m) {
        int u, v, w; cin >> u >> v >> w; --u, --v;
        adj[u].eb(v, w);
        adj[v].eb(u, w);
    }
    rep1(i, (1 << k) - 1) {
        rep(v, n) dist[i][v] = INF;
        if(__builtin_popcount(i) == 1) dist[i][v[__builtin_ctz(i)]] = 0;
        else {
            rep(v, n) for(int j = (i - 1) & i; j; j = (j - 1) & i) {
                dist[i][v] = min(dist[i][v], dist[j][v] + dist[i ^ j][v]);
            }
        }
        priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
        rep(v, n) pq.emplace(dist[i][v], v);
        while(!pq.empty()) {
            auto [chk, u] = pq.top(); pq.pop();
            if(chk != dist[i][u]) continue;
            for(auto& [v, w]: adj[u]) if(dist[i][v] > dist[i][u] + w) {
                dist[i][v] = dist[i][u] + w;
                pq.emplace(dist[i][v], v);
            }
        }
        /*cout << i << '\t';
        rep(v, n) cout << dist[i][v] << ' ';
        cout << endl;*/
    }
    rep1(i, (1 << k) - 1) {
        dp[i] = INF;
        rep(v, n) dp[i] = min(dp[i], dist[i][v]);
        for(int j = (i - 1) & i; j; j = (j - 1) & i) {
            rep(l, n) if((i >> l) & 1) dp[i] = min(dp[i], dp[j | (1 << l)] + dp[(i ^ j) | (1 << l)]);
        }
    }
    cout << dp[(1 << k) - 1] << endl;
}

Compilation message

cities.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization("unroll-loops")
      |

Subtask #1
22.0 / 22.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 484 ms 20860 KB Output is correct
2 Correct 462 ms 20600 KB Output is correct
3 Correct 292 ms 14916 KB Output is correct
4 Correct 53 ms 7404 KB Output is correct
5 Correct 242 ms 17528 KB Output is correct
6 Correct 49 ms 7352 KB Output is correct
7 Correct 4 ms 2892 KB Output is correct
8 Correct 3 ms 2764 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2900 KB Output is correct
2 Correct 6 ms 3000 KB Output is correct
3 Correct 5 ms 2892 KB Output is correct
4 Correct 4 ms 2892 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 980 ms 26908 KB Output is correct
2 Correct 926 ms 27256 KB Output is correct
3 Correct 597 ms 21192 KB Output is correct
4 Correct 507 ms 17780 KB Output is correct
5 Correct 137 ms 9608 KB Output is correct
6 Correct 58 ms 9184 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1892 ms 39468 KB Output is correct
2 Correct 1906 ms 39688 KB Output is correct
3 Correct 1840 ms 39628 KB Output is correct
4 Correct 1235 ms 33820 KB Output is correct
5 Correct 988 ms 24084 KB Output is correct
6 Correct 213 ms 10668 KB Output is correct
7 Correct 67 ms 9332 KB Output is correct