oj.uz

Submission #734229

# Submission time Handle Problem Language Result Execution time Memory
734229 2023-05-02T05:49:16 Z GrindMachine Cities (BOI16_cities) C++17
100 / 100
 5566 ms 227624 KB 
// Om Namah Shivaya

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

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x, y) ((x + y - 1) / (y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i, n) for(int i = 0; i < n; ++i)
#define rep1(i, n) for(int i = 1; i <= n; ++i)
#define rev(i, s, e) for(int i = s; i >= e; --i)
#define trav(i, a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a, b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a, b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*

refs:
https://youtu.be/BG4vAoV5kWw

spiderman algorithm
only works for k <= 5
for k > 5, use steiner tree dp

spiderman algo:
works when the chosen spanning tree is a caterpillar tree
i.e one main chain + 1-node branches from nodes in the main chain
only works for k <= 5

implement with modified dijkstra's

*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

vector<pll> adj[N];

void solve(int test_case)
{
    ll n, k, m; cin >> n >> k >> m;
    vector<ll> a(k);
    rep(i, k) cin >> a[i];

    rep1(i, m) {
        ll u, v, w; cin >> u >> v >> w;
        adj[u].pb({v, w}), adj[v].pb({u, w});
    }

    ll dis[k][n + 5];
    rep(id, k) {
        ll s = a[id];
        priority_queue<pll, vector<pll>, greater<pll>> pq;
        pq.push({0, s});

        vector<bool> vis(n + 5);

        while (!pq.empty()) {
            auto [cost, u] = pq.top();
            pq.pop();

            if (vis[u]) conts;
            vis[u] = 1;
            dis[id][u] = cost;

            for (auto [v, w] : adj[u]) {
                pq.push({cost + w, v});
            }
        }
    }

    ll dp[n + 5][1 << k];
    memset(dp, -1, sizeof dp);

    priority_queue<array<ll, 3>, vector<array<ll, 3>>, greater<array<ll, 3>>> pq;
    pq.push({0, a[0], 1});

    while (!pq.empty()) {
        auto [cost, u, mask] = pq.top();
        pq.pop();

        if (dp[u][mask] != -1) conts;
        dp[u][mask] = cost;

        // continue main chain
        for (auto [v, w] : adj[u]) {
            pq.push({cost + w, v, mask});
        }

        // shoot web
        rep(id, k) {
            if (mask & (1 << id)) conts;
            ll v = a[id];
            ll w = dis[id][u];
            pq.push({cost + w, u, mask | (1 << id)});
        }
    }

    ll ans = inf2;
    rep1(u, n) {
        amin(ans, dp[u][(1 << k) - 1]);
    }

    cout << ans << endl;
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

Compilation message

cities.cpp: In function 'void solve(int)':
cities.cpp:130:16: warning: unused variable 'v' [-Wunused-variable]
  130 |             ll v = a[id];
      |                ^

Subtask #1
22.0 / 22.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1206 ms 56580 KB Output is correct
2 Correct 1117 ms 55744 KB Output is correct
3 Correct 444 ms 24840 KB Output is correct
4 Correct 873 ms 76696 KB Output is correct
5 Correct 599 ms 33792 KB Output is correct
6 Correct 447 ms 51876 KB Output is correct
7 Correct 6 ms 3156 KB Output is correct
8 Correct 5 ms 2992 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3480 KB Output is correct
2 Correct 11 ms 3480 KB Output is correct
3 Correct 7 ms 3196 KB Output is correct
4 Correct 11 ms 3420 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2317 ms 88328 KB Output is correct
2 Correct 2505 ms 87332 KB Output is correct
3 Correct 1138 ms 50580 KB Output is correct
4 Correct 1903 ms 55992 KB Output is correct
5 Correct 1761 ms 127664 KB Output is correct
6 Correct 1682 ms 127988 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5192 ms 150804 KB Output is correct
2 Correct 5241 ms 151048 KB Output is correct
3 Correct 5566 ms 150008 KB Output is correct
4 Correct 2651 ms 88412 KB Output is correct
5 Correct 4253 ms 87240 KB Output is correct
6 Correct 3734 ms 227624 KB Output is correct
7 Correct 3643 ms 226884 KB Output is correct