oj.uz

Submission #734240

# Submission time Handle Problem Language Result Execution time Memory
734240 2023-05-02T06:02:47 Z GrindMachine Cities (BOI16_cities) C++17
100 / 100
 2685 ms 96612 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];
    memset(dis, 0x3f, sizeof dis);

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

        vector<bool> vis(n + 5);

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

            if (vis[u]) conts;
            vis[u] = 1;

            for (auto [v, w] : adj[u]) {
                ll cost2 = cost + w;
                if (cost2 < dis[id][v]) {
                    dis[id][v] = cost2;
                    pq.push({cost2, v});
                }
            }
        }
    }

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

    bool vis[n + 5][1 << k];
    memset(vis, 0, sizeof vis);

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

    dp[a[0]][1] = 0;

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

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

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

        // shoot web
        rep(id, k) {
            if (mask & (1 << id)) conts;
            ll v = a[id];
            ll w = dis[id][u];

            ll cost2 = cost + w;
            ll mask2 = mask | (1 << id);

            if (cost2 < dp[u][mask2]) {
                dp[u][mask2] = cost2;
                pq.push({cost2, u, mask2});
            }
        }
    }

    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:146:16: warning: unused variable 'v' [-Wunused-variable]
  146 |             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 1 ms 2644 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 2644 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 648 ms 36140 KB Output is correct
2 Correct 623 ms 36988 KB Output is correct
3 Correct 317 ms 23632 KB Output is correct
4 Correct 116 ms 12124 KB Output is correct
5 Correct 337 ms 25724 KB Output is correct
6 Correct 57 ms 11824 KB Output is correct
7 Correct 4 ms 3028 KB Output is correct
8 Correct 4 ms 2900 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3224 KB Output is correct
2 Correct 6 ms 3248 KB Output is correct
3 Correct 5 ms 3028 KB Output is correct
4 Correct 4 ms 3028 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1359 ms 56372 KB Output is correct
2 Correct 1184 ms 56892 KB Output is correct
3 Correct 943 ms 49796 KB Output is correct
4 Correct 735 ms 35628 KB Output is correct
5 Correct 198 ms 20140 KB Output is correct
6 Correct 69 ms 14392 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2685 ms 95872 KB Output is correct
2 Correct 2672 ms 95780 KB Output is correct
3 Correct 2201 ms 96612 KB Output is correct
4 Correct 1624 ms 89500 KB Output is correct
5 Correct 1284 ms 55368 KB Output is correct
6 Correct 266 ms 21704 KB Output is correct
7 Correct 74 ms 15112 KB Output is correct