Submission #1272027

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272027		sweetwibu2k8	Džumbus (COCI19_dzumbus)	C++20	0 / 110	27 ms	3224 KiB

dzumbus

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (1LL<<60);

int N, M;
vector<ll> D;
vector<vector<int>> g;

struct Triple {
    vector<ll> dp0; // u NOT chosen: dp0[k] = min cost to have k good nodes in subtree
    vector<ll> dp1; // u chosen but pending (no neighbor chosen yet inside subtree): dp1[k] -> k good nodes in subtree (excluding u)
    vector<ll> dp2; // u chosen and connected (u counted): dp2[k] -> k good nodes in subtree (including u)
};

// DFS returns Triple for subtree rooted at u (parent = p)
Triple dfs(int u, int p) {
    Triple cur;
    cur.dp0 = {0};       // no good nodes, cost 0
    cur.dp1 = {D[u]};    // choose u, but pending (not yet connected), cost D[u], contributes 0 good nodes so far
    cur.dp2 = {};        // impossible initially

    for (int v : g[u]) if (v != p) {
        Triple ch = dfs(v, u);

        int s0 = (int)cur.dp0.size() - 1;
        int s1 = (int)cur.dp1.size() - 1;
        int s2 = (int)cur.dp2.size() - 1;
        int c0 = (int)ch.dp0.size() - 1;
        int c1 = (int)ch.dp1.size() - 1;
        int c2 = (int)ch.dp2.size() - 1;

        int maxChild = max({c0,c1,c2,0});
        int newMax = max({s0,s1,s2,0}) + maxChild + 2; // +2 for transitions that add +2

        vector<ll> ndp0(newMax+1, INF), ndp1(newMax+1, INF), ndp2(newMax+1, INF);

        auto get = [&](const vector<ll>& v, int idx)->ll{
            if (idx < 0 || idx >= (int)v.size()) return INF;
            return v[idx];
        };

        // parent NOT chosen: child can be not chosen (dp0) or child chosen+connected (dp2).
        for (int i = 0; i <= s0; ++i) {
            ll base = get(cur.dp0, i);
            if (base >= INF) continue;
            for (int j = 0; j <= max(c0, c2); ++j) {
                ll chCost = min(get(ch.dp0, j), get(ch.dp2, j));
                if (chCost >= INF) continue;
                ndp0[i + j] = min(ndp0[i + j], base + chCost);
            }
        }

        // parent chosen but pending (dp1)
        // - child dp0 or dp2: parent remains pending
        // - child dp1: if both parent and child pending -> they connect => both counted: +2
        for (int i = 0; i <= s1; ++i) {
            ll base = get(cur.dp1, i);
            if (base >= INF) continue;
            for (int j = 0; j <= max({c0,c1,c2}); ++j) {
                if (get(ch.dp0, j) < INF) ndp1[i + j] = min(ndp1[i + j], base + get(ch.dp0, j));
                if (get(ch.dp2, j) < INF) ndp1[i + j] = min(ndp1[i + j], base + get(ch.dp2, j));
                if (get(ch.dp1, j) < INF) {
                    // child becomes good (+1) and parent becomes good (+1) => +2
                    ndp2[i + j + 2] = min(ndp2[i + j + 2], base + get(ch.dp1, j));
                }
            }
        }

        // parent already connected (dp2)
        // - child dp0 or dp2: add j goods
        // - child dp1: child resolves by parent => child counted (+1)
        if (!cur.dp2.empty()) {
            for (int i = 0; i <= s2; ++i) {
                ll base = get(cur.dp2, i);
                if (base >= INF) continue;
                for (int j = 0; j <= max({c0,c1,c2}); ++j) {
                    if (get(ch.dp0, j) < INF) ndp2[i + j] = min(ndp2[i + j], base + get(ch.dp0, j));
                    if (get(ch.dp2, j) < INF) ndp2[i + j] = min(ndp2[i + j], base + get(ch.dp2, j));
                    if (get(ch.dp1, j) < INF) ndp2[i + j + 1] = min(ndp2[i + j + 1], base + get(ch.dp1, j));
                }
            }
        }

        // trim trailing INF
        auto trim = [&](vector<ll>& v){
            int last = (int)v.size() - 1;
            while (last >= 0 && v[last] >= INF) --last;
            v.resize(last + 1);
        };
        trim(ndp0); trim(ndp1); trim(ndp2);
        if (ndp0.empty()) ndp0 = {INF};
        if (ndp1.empty()) ndp1 = {INF};
        // ndp2 may be empty legitimately

        cur.dp0.swap(ndp0);
        cur.dp1.swap(ndp1);
        cur.dp2.swap(ndp2);
    }

    return cur;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> M;
    D.assign(N, 0);
    for (int i = 0; i < N; ++i) cin >> D[i];
    g.assign(N, {});
    for (int i = 0; i < M; ++i){
        int a,b; cin >> a >> b; --a; --b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    int Q; cin >> Q;
    vector<ll> S(Q);
    for (int i = 0; i < Q; ++i) cin >> S[i];

    vector<int> vis(N,0);
    // comps_best[c] = minimal cost to get c good nodes in that component
    vector<vector<ll>> comps_best;

    for (int i = 0; i < N; ++i) if (!vis[i]) {
        // collect component nodes
        vector<int> stk = {i};
        vis[i] = 1;
        for (int idx = 0; idx < (int)stk.size(); ++idx) {
            int u = stk[idx];
            for (int v : g[u]) if (!vis[v]) { vis[v] = 1; stk.push_back(v); }
        }
        // run tree DP with root i
        Triple t = dfs(i, -1);
        int maxc = 0;
        if (!t.dp0.empty()) maxc = max(maxc, (int)t.dp0.size() - 1);
        if (!t.dp2.empty()) maxc = max(maxc, (int)t.dp2.size() - 1);
        vector<ll> best(maxc + 1, INF);
        for (int c = 0; c <= maxc; ++c) {
            ll val = INF;
            if (c < (int)t.dp0.size()) val = min(val, t.dp0[c]);
            if (c < (int)t.dp2.size()) val = min(val, t.dp2[c]);
            best[c] = val;
        }
        if (best.empty()) best = {0};
        else best[0] = min(best[0], 0LL);
        comps_best.push_back(best);
    }

    // global knapsack by value (number of good nodes)
    vector<ll> global(N+1, INF);
    global[0] = 0;
    for (auto &best : comps_best) {
        vector<ll> nxt(N+1, INF);
        int sz = (int)best.size() - 1;
        for (int have = 0; have <= N; ++have) {
            if (global[have] >= INF) continue;
            for (int c = 0; c <= sz; ++c) {
                if (best[c] >= INF) continue;
                if (have + c <= N) nxt[have + c] = min(nxt[have + c], global[have] + best[c]);
            }
        }
        global.swap(nxt);
    }

    // answer queries: for each S[i], output max v with global[v] <= S[i]
    for (int qi = 0; qi < Q; ++qi) {
        ll s = S[qi];
        int ans = 0;
        for (int v = 0; v <= N; ++v) if (global[v] <= s) ans = v;
        cout << ans << '\n';
    }

    return 0;
}

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