oj.uz

Submission #1105283

# Submission time Handle Problem Language Result Execution time Memory
1105283 2024-10-26T03:14:46 Z thangdz2k7 Cities (BOI16_cities) C++17
100 / 100
 748 ms 42312 KB 
// author : thembululquaUwU
// 3.9.2024

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define endl '\n'

using namespace std;
using ll = long long;
using ii = pair <int, int>;
using lli = pair <ll, int>;
using vi = vector <int>;

const int N = 1e5 + 5;
const int mod = 1e9 + 7;
const ll inf = 1e18;
const int LG = 4;
const int mx = (1 << LG);

void maxl(auto &a, auto b) {a = max(a, b);}
void minl(auto &a, auto b) {a = min(a, b);}

int n, m, k, T, a[LG];
pair <int, int> trace[mx][N];
vector <ii> adj[N];
ll d[mx][N];
priority_queue <lli, vector <lli>, greater <lli>> pq;

#define Mask(i)  (1 << (i))
#define Bit(x, i)  ((x) >> (i) & 1)
#define bp __builtin_popcount
#define bpll __builtin_popcountll

struct Edge{
    int u, v, mask;
};

vector <Edge> ans;

void dfs(int mask, int u){
    auto [m1, m2] = trace[mask][u];
    if (!m1) return;
    if (m1 == mask){
        ans.push_back({m2, u, mask});
        dfs(m1, m2);
    }
    else {
        dfs(m1, u);
        dfs(m2, u);
    }
}

void solve(){
    cin >> n >> k >> m;
    for (int i = 0; i < k; ++ i) cin >> a[i];
    T = a[k - 1]; -- k;
    while (m --){
        int u, v, w; cin >> u >> v >> w;
        adj[u].pb({w, v});
        adj[v].pb({w, u});
    }

    int tae = (1 << k);
    for (int mask = 1; mask < tae; ++ mask){
        for (int i = 1; i <= n; ++ i) d[mask][i] = inf;
        if (bp(mask) == 1) {
            d[mask][a[__lg(mask)]] = 0;
            trace[mask][a[__lg(mask)]] = {0, 0};
        }
        for (int i = 1; i <= n; ++ i){
            for (int j = (mask - 1) & mask; j; j = (j - 1) & mask){
                if (d[mask][i] > d[j][i] + d[mask - j][i]){
                    d[mask][i] = d[j][i] + d[mask - j][i];
                    trace[mask][i] = {j, mask - j};
                }
            }
            pq.push({d[mask][i], i});
        }

        while (pq.size()){
            auto [du, u] = pq.top(); pq.pop();
            if (du != d[mask][u]) continue;
            for (auto [w, v] : adj[u]){
                if (d[mask][v] > du + w){
                    d[mask][v] = du + w;
                    trace[mask][v] = {mask, u};
                    pq.push({d[mask][v], v});
                }
            }
        }
    }

    cout << d[tae - 1][T] << endl;
//    dfs(tae - 1, T);
//    reverse(ans.begin(), ans.end());
//    cout << ans.size() << endl;
//    for (auto [u, v, mask] : ans){
//        for (int i = 0; i < k; ++ i) cout << Bit(mask, i);
//        cout << ' ' << u << ' ' << v << endl;
//    }
}

int main(){
    if (fopen("taxi.inp", "r")){
        freopen("taxi.inp", "r", stdin);
        freopen("taxi.out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int t = 1; // cin >> t;
    while (t --) solve();
    return 0;
}

Compilation message

cities.cpp:22:11: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   22 | void maxl(auto &a, auto b) {a = max(a, b);}
      |           ^~~~
cities.cpp:22:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   22 | void maxl(auto &a, auto b) {a = max(a, b);}
      |                    ^~~~
cities.cpp:23:11: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   23 | void minl(auto &a, auto b) {a = min(a, b);}
      |           ^~~~
cities.cpp:23:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   23 | void minl(auto &a, auto b) {a = min(a, b);}
      |                    ^~~~
cities.cpp: In function 'int main()':
cities.cpp:107:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |         freopen("taxi.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
cities.cpp:108:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |         freopen("taxi.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6480 KB Output is correct
2 Correct 2 ms 6648 KB Output is correct
3 Correct 2 ms 10744 KB Output is correct
4 Correct 2 ms 14840 KB Output is correct
5 Correct 3 ms 26960 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 25268 KB Output is correct
2 Correct 180 ms 24936 KB Output is correct
3 Correct 94 ms 18112 KB Output is correct
4 Correct 39 ms 18760 KB Output is correct
5 Correct 96 ms 23232 KB Output is correct
6 Correct 43 ms 14664 KB Output is correct
7 Correct 3 ms 10832 KB Output is correct
8 Correct 2 ms 6736 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 14928 KB Output is correct
2 Correct 4 ms 14928 KB Output is correct
3 Correct 3 ms 14672 KB Output is correct
4 Correct 4 ms 15096 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 30900 KB Output is correct
2 Correct 353 ms 31144 KB Output is correct
3 Correct 220 ms 24248 KB Output is correct
4 Correct 230 ms 28856 KB Output is correct
5 Correct 82 ms 23876 KB Output is correct
6 Correct 53 ms 24672 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 748 ms 41904 KB Output is correct
2 Correct 689 ms 42312 KB Output is correct
3 Correct 677 ms 42120 KB Output is correct
4 Correct 416 ms 35000 KB Output is correct
5 Correct 443 ms 39352 KB Output is correct
6 Correct 116 ms 36284 KB Output is correct
7 Correct 52 ms 36936 KB Output is correct