Submission #1305865

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305865		orzorzorz	Fireworks (APIO16_fireworks)	C++20	0 / 100	2 ms	572 KiB

fireworks

#include <bits/stdc++.h>
using namespace std;

static const long long INF = (1LL << 60);

struct Edge {
    int to;
    long long w;
};

int N;
vector<vector<Edge>> tree;
vector<long long> leafDist;      // distances from root to leaves
vector<long long> vals;          // candidate T values
unordered_map<long long, int> id; // value -> index

vector<vector<long long>> dp;

/* Step 1: compute root->leaf distances */
void dfs_dist(int u, int parent, long long dist) {
    bool isLeaf = true;
    for (auto &e : tree[u]) {
        if (e.to == parent) continue;
        isLeaf = false;
        dfs_dist(e.to, u, dist + e.w);
    }
    if (isLeaf) leafDist.push_back(dist);
}

/* Step 2: tree DP */
void dfs_dp(int u, int parent) {
    bool isLeaf = true;

    for (auto &e : tree[u]) {
        if (e.to == parent) continue;
        isLeaf = false;
        dfs_dp(e.to, u);
    }

    int M = vals.size();
    dp[u].assign(M, 0);

    if (isLeaf) {
        // base case
        for (int i = 0; i < M; i++) {
            dp[u][i] = llabs(vals[i]);
        }
        return;
    }

    // internal node
    for (int i = 0; i < M; i++) {
        long long T = vals[i];
        long long cost = 0;

        for (auto &e : tree[u]) {
            if (e.to == parent) continue;

            long long best = INF;
            for (int j = 0; j < M; j++) {
                long long x = vals[j];
                long long need = T - x;
                if (!id.count(need)) continue;

                int idx = id[need];
                best = min(best,
                    dp[e.to][idx] + llabs(x - e.w));
            }
            cost += best;
        }

        dp[u][i] = cost;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N;
    tree.resize(N + 1);

    for (int i = 1; i < N; i++) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        tree[u].push_back({v, w});
        tree[v].push_back({u, w});
    }

    // collect leaf distances
    dfs_dist(1, 0, 0);

    // unique candidate T values
    sort(leafDist.begin(), leafDist.end());
    leafDist.erase(unique(leafDist.begin(), leafDist.end()), leafDist.end());
    vals = leafDist;

    for (int i = 0; i < (int)vals.size(); i++)
        id[vals[i]] = i;

    dp.resize(N + 1);
    dfs_dp(1, 0);

    long long ans = INF;
    for (long long x : dp[1]) ans = min(ans, x);

    cout << ans << "\n";
    return 0;
}

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