oj.uz

Submission #878029

# Submission time Handle Problem Language Result Execution time Memory
878029 2023-11-24T02:51:18 Z bobbilyking Cities (BOI16_cities) C++17
14 / 100
 432 ms 98968 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>{*want.begin()}};
    }  else if (want.size() <= 3) {
        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 {
        // pick a partition of nodes to do
        F(bm, 1, 1<<want.size()) {
            vector<ll> w, w2;
            F(i, 0, want.size()) (bool((1<<i)&bm) ? w: w2).push_back(want[i]);
            auto [r1, d1] = dfs(w);
            auto [r2, d2] = dfs(w2);
            ll total = r1 + r2;

            auto d3 = dij({d1}); auto d4 = dij({d2});
            set<ll> new_nodes(A(d3)); for (auto y: d4) new_nodes.insert(y);
            ll ans = 1e18;
            set<ll> pot;
            F(i, 1, n+1) {
                if (d3[i] + d4[i] < ans) {
                    ans = d3[i] + d4[i]; pot.clear();
                } 
                pot.insert(i);
            }  
            for (auto x: pot) new_nodes.insert(x);
            return {ans, new_nodes};
        }
    }
    assert(false);
}

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:71:13: note: in expansion of macro 'F'
   71 |             F(i, 0, want.size()) (bool((1<<i)&bm) ? w: w2).push_back(want[i]);
      |             ^
cities.cpp:74:16: warning: unused variable 'total' [-Wunused-variable]
   74 |             ll total = r1 + r2;
      |                ^~~~~

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Incorrect 1 ms 2808 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 22400 KB Output is correct
2 Correct 146 ms 22948 KB Output is correct
3 Correct 49 ms 13120 KB Output is correct
4 Correct 44 ms 15296 KB Output is correct
5 Correct 139 ms 21600 KB Output is correct
6 Correct 44 ms 15248 KB Output is correct
7 Correct 2 ms 2908 KB Output is correct
8 Correct 2 ms 3168 KB Output is correct

Subtask #3
0 / 15.0

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

Subtask #4
0 / 23.0

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

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 432 ms 98968 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -