oj.uz

Submission #349161

# Submission time Handle Problem Language Result Execution time Memory
349161 2021-01-16T20:41:23 Z ijxjdjd Cities (BOI16_cities) C++14
100 / 100
 4547 ms 108600 KB 
#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#define FR(i, N) for (int i = 0; i < int(N); i++)
using namespace std;

using ll = long long;

struct State {
    ll d;
    int msk, i;
    bool operator<(const State& rhs) const {
        return rhs.d < d;
    }
};
const int MAXN = (int)(1e5)+5;
const int MAXK = 5;
int st[MAXK];
int to[MAXN];
ll dist[MAXN][1<<MAXK];
const ll INF = (ll)(1e18);
vector<pair<int, ll>> adj[MAXN];
int main() {
	cin.tie(0);
	cin.sync_with_stdio(0);
	int N, k, M;
	cin >> N >> k >> M;
	FR(i, k) {
        cin >> st[i];
        st[i]--;
        to[st[i]] = i;
	}
	int cnt = k;
	FR(i, N){
        if (find(st, st+k, i) == (st + k)) {
            to[i] = cnt++;
        }
	}
	priority_queue<State> pq;
	FR(i, N) {
        FR(j, 1<<k) {
            dist[i][j] = INF;
        }
        if (i < k) {
            dist[i][1<<i] = 0;
            pq.push({0, 1<<i, i});
        }
	}
	FR(i, M) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        a = to[a];
        b = to[b];
        ll w;
        cin >> w;
        adj[a].push_back({b, w});
        adj[b].push_back({a, w});
	}
	while (pq.size()) {
        auto[d, msk, i] = pq.top(); pq.pop();
        if (msk == (1<<k)-1) {
            break;
        }
        if (dist[i][msk] == d) {
            for (auto[e, w] : adj[i]) {
                if (dist[e][msk] > d+w) {
                    dist[e][msk] = d+w;
                    pq.push({dist[e][msk], msk, e});
                }
            }
            for (int j = 0; j < k; j++) {
                if (dist[i][msk|(1<<j)] > dist[i][1<<j] + d) {
                    dist[i][msk|(1<<j)] = dist[i][1<<j] + d;
                    pq.push({dist[i][msk|(1<<j)], msk|(1<<j), i});
                }
            }
        }
	}
	ll ans = INF;
	FR(i, N) {
        ans = min(ans, dist[i][(1<<k)-1]);
	}
	cout << ans << '\n';
	return 0;
}

Compilation message

cities.cpp: In function 'int main()':
cities.cpp:62:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   62 |         auto[d, msk, i] = pq.top(); pq.pop();
      |             ^
cities.cpp:67:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   67 |             for (auto[e, w] : adj[i]) {
      |                      ^

Subtask #1
22.0 / 22.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 566 ms 51032 KB Output is correct
2 Correct 584 ms 50184 KB Output is correct
3 Correct 147 ms 36836 KB Output is correct
4 Correct 77 ms 16092 KB Output is correct
5 Correct 301 ms 47072 KB Output is correct
6 Correct 68 ms 15596 KB Output is correct
7 Correct 5 ms 3244 KB Output is correct
8 Correct 3 ms 3180 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3436 KB Output is correct
2 Correct 8 ms 3436 KB Output is correct
3 Correct 5 ms 3180 KB Output is correct
4 Correct 5 ms 3180 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1902 ms 75904 KB Output is correct
2 Correct 1552 ms 74736 KB Output is correct
3 Correct 970 ms 52148 KB Output is correct
4 Correct 1035 ms 46664 KB Output is correct
5 Correct 196 ms 26428 KB Output is correct
6 Correct 91 ms 18280 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4444 ms 108600 KB Output is correct
2 Correct 4547 ms 108568 KB Output is correct
3 Correct 4106 ms 107628 KB Output is correct
4 Correct 1950 ms 68532 KB Output is correct
5 Correct 2608 ms 63388 KB Output is correct
6 Correct 505 ms 26560 KB Output is correct
7 Correct 118 ms 18660 KB Output is correct