oj.uz

Submission #878081

# Submission time Handle Problem Language Result Execution time Memory
878081 2023-11-24T04:46:47 Z bobbilyking Cities (BOI16_cities) C++17
74 / 100
 6000 ms 23992 KB 
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")

#include<bits/stdc++.h>
#include<math.h>
using namespace std;

typedef long long int ll;
typedef long double ld;
typedef pair<ll, ll> pl;
typedef vector<ll> vl;
#define FD(i, r, l) for(ll i = r; i > (l); --i)

#define K first
#define V second
#define G(x) ll x; cin >> x;
#define GD(x) ld x; cin >> x;
#define GS(s) string s; cin >> s;
#define EX(x) { cout << x << '\n'; exit(0); }
#define A(a) (a).begin(), (a).end()
#define F(i, l, r) for (ll i = l; i < (r); ++i)

#define NN
#define M 1000000007 // 998244353

ll n;
vector<pl> adj[100010];

vector<ll> dij(set<ll> in) {
    vector<ll> res(n+1);
    vector<ll> dist(n+1, 1e18);
    priority_queue<pl, vector<pl>, greater<pl>> q;
    for (auto a: in) {
        q.emplace(0, a);  
        dist[a] = 0;
    }

    while (q.size()) {
        auto [d, h] = q.top(); q.pop();
        if (dist[h] != d) continue;

        for (auto [x, w]: adj[h]) if (dist[h] + w < dist[x]) {
            dist[x] = dist[h] + w;
            q.emplace(dist[x], x);
        }
    }

    return dist;     
}

pair<ll, set<ll>> dfs(vector<ll> want) {
    assert(want.size());
    if (want.size() == 1) {
        return {0, set<ll>(A(want))};
    } else if (want.size() == 2) {
        vector<vector<ll>> dist;
        for (auto x: want) dist.push_back(dij({x})); 
        ll r = 1e18;
        set<ll> nodes;
        F(i, 1, n+1) {
            ll x = 0; for (auto &d: dist) x += d[i];
            if (x < r) nodes.clear(), r = x;
            if (r == x) nodes.insert(i);  
        }
        return {r, nodes};
    }
    else if (want.size() <= 3) {
        vector<vector<ll>> dist;
        for (auto x: want) dist.push_back(dij({x})); 
        ll r = 1e18;
        ll optimalNode = -1;
        F(i, 1, n+1) {
            ll x = 0; for (auto &d: dist) x += d[i];
            if (x < r) {
                r = x;
                optimalNode = i;
            }
        }
        auto dOpt = dij({optimalNode}); 
        set<ll> nodes;
        F(i, 1, n+1) { // if any are optimal ,add this
            for (auto &d: dist) if (d[i] + dOpt[i] == d[optimalNode]) nodes.insert(i);
        }
        return {r, nodes};
    } else {
        // pick a partition of nodes to do
        pair<ll, set<ll>> best = {1e18, {}};
        F(bm, 1, (1<<want.size())-1) {
            vector<ll> w, w2;
            F(i, 0, want.size()) (bool((1<<i)&bm) ? w: w2).push_back(want[i]);
            // if (min(w.size(), w2.size()) == 1) continue;  
            auto [r1, fixed_set1] = dfs(w);
            auto [r2, fixed_set2] = dfs(w2);
            ll total = r1 + r2;

            auto d3 = dij(fixed_set1); auto d4 = dij(fixed_set2);
            ll ans = 1e18;
            set<ll> pot;
            F(i, 1, n+1) {
                if (d3[i] + d4[i] < ans) {
                    ans = d3[i] + d4[i]; pot.clear();
                } 
                if (d3[i] + d4[i] == ans) pot.insert(i);
            }  
            best = min(best, {ans + total, {}});
        }
        return best;
    }
}

int main(){
//    freopen("a.in", "r", stdin);
//    freopen("a.out", "w", stdout);

    ios_base::sync_with_stdio(false); cin.tie(0);
    cout << fixed << setprecision(20);
    cin >> n; G(k) G(m)
    vector<ll> v;
    F(i, 0, k) {
        G(x) v.push_back(x);
    } 
    while (m--) {
        G(x) G(y) G(w)
        adj[x].emplace_back(y, w);
        adj[y].emplace_back(x, w);
    }   

    cout << dfs(v).K << '\n';
}

Compilation message

cities.cpp: In function 'std::pair<long long int, std::set<long long int> > dfs(std::vector<long long int>)':
cities.cpp:22:37: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 | #define F(i, l, r) for (ll i = l; i < (r); ++i)
      |                                     ^
cities.cpp:91:13: note: in expansion of macro 'F'
   91 |             F(i, 0, want.size()) (bool((1<<i)&bm) ? w: w2).push_back(want[i]);
      |             ^

Subtask #1
22.0 / 22.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 18692 KB Output is correct
2 Correct 176 ms 19388 KB Output is correct
3 Correct 60 ms 11916 KB Output is correct
4 Correct 46 ms 11784 KB Output is correct
5 Correct 125 ms 17248 KB Output is correct
6 Correct 43 ms 11788 KB Output is correct
7 Correct 2 ms 3104 KB Output is correct
8 Correct 2 ms 2904 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 2908 KB Output is correct
2 Correct 12 ms 3012 KB Output is correct
3 Correct 5 ms 2904 KB Output is correct
4 Correct 9 ms 2908 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2556 ms 19168 KB Output is correct
2 Correct 2588 ms 23992 KB Output is correct
3 Correct 670 ms 16308 KB Output is correct
4 Correct 1528 ms 21448 KB Output is correct
5 Correct 512 ms 16900 KB Output is correct
6 Correct 123 ms 17420 KB Output is correct

Subtask #5
0 / 26.0

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