Submission #403845

#	Time	Username	Problem	Language	Result	Execution time	Memory
403845		CrouchingDragon	Džumbus (COCI19_dzumbus)	C++17	50 / 110	80 ms	1884 KiB

dzumbus

#include "bits/stdc++.h"

using namespace std;

#define endl '\n'
#define debug(x) cerr << #x << " == " << (x) << '\n';
#define all(x) begin(x), end(x)

using ll = long long;

const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;

template<typename T>
void chmin(T& x, T y) { x = min(x, y); }

const int L = 1e7, R = 1e9;

mt19937 rng((int) chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<int> unif(L, R);

// trees will most likely have O(log(n)) height
// also, connected graphs will have O(log(n)) diameter
// number of edges is not exact, specially with small graphs
// make sure to relabel, catches stupid bugs
// 0-based

auto tree_generator(int n) {
    vector<pair<int, int>> edges;
    for (int u = 1; u < n; ++u) edges.emplace_back(unif(rng) % u, u);
    return edges;
}

auto graph_generator(int n, int m) {
    vector<pair<int, int>> edges;
    for (int j = 0; j < m; ++j) {
        int u = unif(rng) % n, v = unif(rng) % n;
        if (u == v) continue;
        if (u > v) swap(u, v);
        edges.emplace_back(u, v);
    }
    sort(all(edges)), edges.erase(unique(all(edges)), end(edges));
    return edges;
}

auto connected_graph_generator(int n, int m) {
    assert(m >= n - 1);

    auto tree = tree_generator(n);
    auto edges = graph_generator(n, m - (n - 1));

    edges.insert(end(edges), all(tree));
    sort(all(edges)), edges.erase(unique(all(edges)), end(edges));

    return edges;
}

void relabel(int n, auto& edges) {
    vector<int> label(n, 0);
    iota(all(label), 0);
    shuffle(all(label), rng);
    for (auto& [u, v] : edges) u = label[u], v = label[v];
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N, M;
    cin >> N >> M;

    vector<int> D(N);
    for (auto& x : D) cin >> x;

    vector<vector<int>> E(N);
    for (int i = 0; i < N - 1; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        E[u].push_back(v), E[v].push_back(u);
    }

    vector<bool> vis(N, false);
    auto dfs = [&](auto&& self, int u) -> vector<array<ll, 2>> {
        vis[u] = true;
        vector<array<ll, 2>> dp = {{0LL, LINF}, {LINF, LINF}};
        for (auto v : E[u]) if (not vis[v]) {
            auto dpv = self(self, v);
            int k = (int)size(dp), l = (int)size(dpv);
            vector<array<ll, 2>> dpnxt(k + l - 1, {LINF, LINF});
            int add[4] = {D[u] + D[v], D[v], D[u], 0}, b[4] = {2, 1, 1, 0};
            for (int i = 0; i < k; ++i) {
                for (int j = 0; j < l; ++j) {
                    for (int mask = 0; mask < 4; ++mask) {
                        int s = mask & 1, t = mask >> 1 & 1;
                        chmin(dpnxt[i + j][s], dp[i][s] + dpv[j][t]);
                        if (i + j + b[mask] < k + l - 1) {
                            chmin(dpnxt[i + j + b[mask]][1], dp[i][s] + dpv[j][t] + add[mask]);
                        }
                    }
                }
            }
            swap(dp, dpnxt);
        }
        return dp;
    };

    vector<ll> dp(1, 0);

    for (int u = 0; u < N; ++u) {
        if (vis[u]) continue;
        debug(u);
        auto comp = dfs(dfs, u);
        int k = (int)size(dp), l = (int)size(comp);
        vector<ll> dpnxt(k + l - 1, LINF), add(l);
        for (int j = 0; j < l; ++j) add[j] = min(comp[j][0], comp[j][1]);
        for (int i = 0; i < k; ++i) {
            for (int j = 0; j < l; ++j) {
                chmin(dpnxt[i + j], dp[i] + add[j]);
            }
        }
        swap(dp, dpnxt);
    }

    for (int i = (int)size(dp) - 2; i >= 0; --i) {
        dp[i] = min(dp[i], dp[i + 1]);
    }

    int Q;
    cin >> Q;
    for (int z = 0; z < Q; ++z) {
        ll S;
        cin >> S;
        int ans = (int)distance(begin(dp), upper_bound(all(dp), S)) - 1;
        cout << ans << endl;
    }

    exit(0);
}

Compilation message (stderr)

dzumbus.cpp:58:21: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   58 | void relabel(int n, auto& edges) {
      |                     ^~~~

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30