Submission #995742

#	Time	Username	Problem	Language	Result	Execution time	Memory
995742		avighna	Fireworks (APIO16_fireworks)	C++17	26 / 100	20 ms	1260 KiB

fireworks

#include <bits/stdc++.h>

typedef long long ll;

const ll inf = 1e15;

int main() {
    // std::ios_base::sync_with_stdio(false);
    // std::cin.tie(nullptr);

    ll n, m;
    std::cin >> n >> m;
    std::vector<std::vector<std::pair<ll, ll>>> adj(n + m + 1);
    std::vector<ll> arr;
    for (ll i = 2, p, c; i <= n + m; ++ i) {
        std::cin >> p >> c;
        arr.push_back(c);
        adj[i].push_back({p, c});
        adj[p].push_back({i, c});
    }

    if (n == 1) {
        std::sort(arr.begin(), arr.end());
        ll ans = 0;
        for (auto &i : arr) {
            ans += std::abs(arr[arr.size() / 2] - i);
        }
        std::cout << ans << "\n";
        return 0;
    }
    if (n + m <= 300) {
        std::vector<ll> nodes;
        std::vector<ll> pars(n + m + 1);
        std::function<void(ll, ll)> topological_sort;
        topological_sort = [&](ll node, ll par) {
            pars[node] = par;
            for (auto &i : adj[node]) {
                if (i.first == par) continue;
                topological_sort(i.first, node);
            }
            nodes.push_back(node);
        };
        topological_sort(1, 0);

        std::vector<std::vector<ll>> dp(n + m + 1, std::vector<ll>(301));
        for (ll val = 0; val <= 300; ++ val) {
            for (auto &node : nodes) {
                ll node_cnt = 0;
                for (auto &child : adj[node]) {
                    if (child.first == pars[node]) continue;
                    node_cnt++;
                    ll cur = inf;
                    for (ll i = 0; i <= val; ++ i) {
                        cur = std::min(cur, std::abs(child.second - i) + dp[child.first][val - i]);
                    }
                    dp[node][val] += cur;
                }
                if (node_cnt == 0) dp[node][val] = inf * (val != 0);
                else if (dp[node][val] > inf) dp[node][val] = inf;
            }
        }

        ll ans = inf;
        for (ll val = 0; val <= 300; ++ val) {
            ans = std::min(ans, dp[1][val]);
        }
        std::cout << ans << "\n";
        return 0;
    }
}

• Subtask 1: 7 / 7
• Subtask 2: 19 / 19
• Subtask 3: 0 / 29
• Subtask 4: 0 / 45