oj.uz

Submission #480356

# Submission time Handle Problem Language Result Execution time Memory
480356 2021-10-15T18:15:47 Z hidden1 Cities (BOI16_cities) C++14
74 / 100
 6000 ms 76648 KB 
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e15 + 7;
 
const ll MAX_N = 2e5 + 10, MAX_K = 5;
ll spec[MAX_K];
ll dist[MAX_K][MAX_N];
ll ans[MAX_N][1 << (MAX_K - 2)];
ll n, k, m;
vector<pair<ll, ll> > g[MAX_N];

void calculate(ll ind) {
    for(ll i = 0; i < MAX_N; i ++) {
        dist[ind][i] = mod;
    }
    dist[ind][spec[ind]] = 0;
    priority_queue<pair<ll, ll> > pq;
    pq.push({0, spec[ind]});

    while(!pq.empty()) {
        auto curr = pq.top(); pq.pop();
        curr.first *= -1;

        if(curr.first != dist[ind][curr.second]) {continue;}
        for(auto it : g[curr.second]) {
            if(dist[ind][it.first] > curr.first + it.second) {
                dist[ind][it.first] = curr.first + it.second;
                pq.push({-dist[ind][it.first], it.first});
            }
        }
    }
}

ll getAns(ll start, ll finish) {
    for(ll i = 0; i < MAX_N; i ++) {
        for(ll j = 0; j < (1 << (MAX_K - 2)); j ++) {
            ans[i][j] = mod;
        }
    }

    ans[spec[start]][0] = 0;
    priority_queue<pair<ll, pair<ll, ll> > > pq;
    pq.push({0, {spec[start], 0}});

    while(!pq.empty()) {
        auto curr = pq.top(); pq.pop();

        curr.first *= -1;

        for(auto it : g[curr.second.first]) {
            if(ans[it.first][curr.second.second] > curr.first + it.second) {
                ans[it.first][curr.second.second] = curr.first + it.second;
                pq.push({-ans[it.first][curr.second.second], {it.first, curr.second.second}});
            }            
        }

        for(ll i = 0, skip = 0; i < k; i ++) {
            if(i == start || i == finish) {skip ++; continue;}
            if(ans[curr.second.first][curr.second.second | (1 << (i - skip))] > curr.first + dist[i][curr.second.first]) {
                ans[curr.second.first][curr.second.second | (1 << (i - skip))] = curr.first + dist[i][curr.second.first];
                pq.push({-ans[curr.second.first][curr.second.second | (1 << (i - skip))], {curr.second.first, curr.second.second | (1 << (i - skip))}});
            }            
        }
    }

    return ans[spec[finish]][(1 << (k - 2)) - 1];
}

signed main() {
    // ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> k >> m;
    for(ll i = 0; i < k; i ++) {
        cin >> spec[i];
    }
    for(ll i = 0; i < m; i ++) {
        ll a, b, c;
        cin >> a >> b >> c;
        g[a].push_back({b, c});
        g[b].push_back({a, c});
    }
    for(ll i = 0; i < k; i ++) {
        calculate(i);
    }
    ll ret = mod;
    for(ll i = 0; i < k; i ++) {
        for(ll j = i + 1; j < k; j ++) {
            chkmin(ret, getAns(i, j));
        }
    }
    cout << ret << endl;
    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 20556 KB Output is correct
2 Correct 11 ms 20556 KB Output is correct
3 Correct 15 ms 22220 KB Output is correct
4 Correct 22 ms 23792 KB Output is correct
5 Correct 32 ms 25392 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1052 ms 42064 KB Output is correct
2 Correct 1028 ms 46308 KB Output is correct
3 Correct 498 ms 32352 KB Output is correct
4 Correct 236 ms 35044 KB Output is correct
5 Correct 423 ms 38056 KB Output is correct
6 Correct 217 ms 33184 KB Output is correct
7 Correct 19 ms 22348 KB Output is correct
8 Correct 14 ms 20828 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 24076 KB Output is correct
2 Correct 32 ms 24076 KB Output is correct
3 Correct 26 ms 23960 KB Output is correct
4 Correct 29 ms 24016 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3847 ms 54876 KB Output is correct
2 Correct 3085 ms 57204 KB Output is correct
3 Correct 2378 ms 43008 KB Output is correct
4 Correct 2120 ms 49448 KB Output is correct
5 Correct 582 ms 42552 KB Output is correct
6 Correct 256 ms 38688 KB Output is correct

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6054 ms 76648 KB Time limit exceeded
2 Halted 0 ms 0 KB -