oj.uz

Submission #878093

# Submission time Handle Problem Language Result Execution time Memory
878093 2023-11-24T05:06:07 Z bobbilyking Cities (BOI16_cities) C++17
74 / 100
 2013 ms 31668 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> dijcache[100010];

vector<ll> dij(vector<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);
        }
    }

    if (in.size() == 1) dijcache[in[0]] = dist;

    return dist;     
}

pair<ll, vector<ll>> dfs(vector<ll> want) {
    assert(want.size());
    if (want.size() == 1) {
        return {0, want};
    } else if (want.size() == 2) {
        ll r = 1e18;
        vector<ll> nodes;
        F(i, 1, n+1) {
            ll x = 0; for (auto d: want) x += dijcache[d][i];
            if (x < r) nodes.clear(), r = x;
            if (r == x) nodes.push_back(i);  
        }
        return {r, nodes};
    }
    else if (want.size() <= 3) {
        ll r = 1e18;
        ll optimalNode = -1;
        F(i, 1, n+1) {
            ll x = 0; for (auto d: want) x += dijcache[d][i];
            if (x < r) {
                r = x;
                optimalNode = i;
            }
        }
        auto dOpt = dij({optimalNode}); 
        vector<ll> nodes;
        F(i, 1, n+1) { // if any are optimal ,add this
            for (auto d: want) if (dijcache[d][i] + dOpt[i] == dijcache[d][optimalNode]) {
                nodes.push_back(i); break;
            }
        }
        return {r, nodes};
    } else {
        // pick a partition of nodes to do
        ll bans = 1e18; vector<ll> ansset;
        bitset<100010> opt = {};
        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 (want.size() == 5 and 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;
            vector<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.push_back(i);
            }  
            
            ans += total;
            if (bans > ans) {
                bans = ans;
                opt.reset();
                for (auto x: fixed_set1) opt[x]=1;
                for (auto x: fixed_set2) opt[x]=1;
                for (auto x: pot) opt[x]=1;
            }
        }
        F(i, 1, n+1) if (opt[i]) ansset.push_back(i);
        return {bans, ansset};
    }
}

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(k); for (auto &x: v) cin >> x;
    while (m--) {
        G(x) G(y) G(w)
        adj[x].emplace_back(y, w);
        adj[y].emplace_back(x, w);
    }   
    for (auto x: v) dij({x});

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

Compilation message

cities.cpp: In function 'std::pair<long long int, std::vector<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:93:13: note: in expansion of macro 'F'
   93 |             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 2 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 5164 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 21156 KB Output is correct
2 Correct 176 ms 21776 KB Output is correct
3 Correct 57 ms 14900 KB Output is correct
4 Correct 51 ms 14188 KB Output is correct
5 Correct 119 ms 19536 KB Output is correct
6 Correct 44 ms 14084 KB Output is correct
7 Correct 3 ms 5212 KB Output is correct
8 Correct 2 ms 5116 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5212 KB Output is correct
2 Correct 7 ms 5212 KB Output is correct
3 Correct 4 ms 5212 KB Output is correct
4 Correct 6 ms 5212 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1285 ms 26380 KB Output is correct
2 Correct 1181 ms 24348 KB Output is correct
3 Correct 382 ms 19032 KB Output is correct
4 Correct 722 ms 21860 KB Output is correct
5 Correct 277 ms 15828 KB Output is correct
6 Correct 81 ms 16208 KB Output is correct

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 2013 ms 31668 KB Output isn't correct
2 Halted 0 ms 0 KB -