Submission #878082

#	Time	Username	Problem	Language	Result	Execution time	Memory
878082		bobbilyking	Cities (BOI16_cities)	C++17	14 / 100	5191 ms	19376 KiB

cities

#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 (stderr)

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: 0 / 22
• Subtask 2: 14 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 26