Submission #1305886

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305886		orzorzorz	Fireworks (APIO16_fireworks)	C++20	7 / 100	4 ms	580 KiB

fireworks

/**
 * APIO 2016 - Fireworks
 * 55 Point Solution: DP with Vectors (Slope Trick Basics)
 * * Strategy:
 * 1. Represents the cost function as a list of "breakpoints" (where slope changes).
 * 2. Merging subtrees = Concatenating vectors and Sorting.
 * 3. Edge extension = Trimming the vector (limiting slope) and shifting top 2 points.
 */

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

const int MAXN = 300005;

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

vector<Edge> adj[MAXN];
long long total_edge_sum = 0;

// DP State: The breakpoints of the slope function for the subtree
// The slope starts at -(number_of_leaves) and increases by 1 at each point in this vector.
vector<long long> dp[MAXN];

void solve(int u) {
    // Base case: Leaf node
    if (adj[u].empty()) {
        // Cost is |x - 0|, breakpoints at 0, 0
        dp[u] = {0, 0};
        return;
    }

    // 1. Merge Step: Collect all breakpoints from children
    // Using a single vector for 'u' and appending children's data
    for (auto& e : adj[u]) {
        int v = e.to;
        long long w = e.weight;
        
        solve(v); // Recursive call
        
        // Processing the child edge 'w' immediately before merging
        // We need to transform the child's function for the edge (v -> u)
        
        // Step A: Limit max slope to 1.
        // The child v currently has slope ending at +1 (if it was processed correctly).
        // Actually, let's look at the pattern:
        // A standard node vector has points covering slope -Leaves ... +Leaves.
        // We want to limit it to slope 1 for the optimal range.
        // This means we keep (Leaves + 1) points.
        
        // Note: To simplify, we can process the edge logic *inside* the child vector
        // before appending to the parent.
        
        long long current_leaves = dp[v].size() / 2; // Approximation, or track explicitly
        // Actually, specific property: slope increases by 1 per point.
        // Start slope is -K. To reach slope 1, we need K+1 points.
        // Size is 2K. We remove K-1 points from the back.
        // Simpler: Keep popping until size is (Initial_Size / 2) + 1.
        
        // However, standard logic is:
        // Pop largest points until slope is 1.
        // Then shift largest 2 points by W.
        
        // Let's refine the logic:
        // dp[v] is sorted.
        // We pop back until we hit the "slope 1" boundary.
        // Because we started with slope -K and have 2K points (ending slope +K),
        // we essentially want to keep the first K+1 points.
        
        while (dp[v].size() > (dp[v].size() / 2) + 1) { 
            // This condition is tricky if size changes.
            // Let's use the property: we always remove 2 points and add 2 points
            // in the "shift" step, but the "limit slope" step removes points.
            // Correct Logic: 
            // 1. Pop everything that makes slope > 1.
            // 2. Take top 2, shift by w.
            
            // Wait, simple vector concatenation is expensive if we copy every time.
            // But for 55 points, this is acceptable.
            
            // Let's just follow the logic:
            // Remove points until slope 1.
            // Start slope = -(size/2). End slope = +(size/2).
            // We want End slope = 1.
            // We need to remove (End_Slope - 1) points?
            // Yes.
            dp[v].pop_back(); 
        }
        
        // Step B: Shift the optimal range
        long long b = dp[v].back(); dp[v].pop_back();
        long long a = dp[v].back(); dp[v].pop_back();
        
        dp[v].push_back(a + w);
        dp[v].push_back(b + w);
        
        // Merge into parent
        dp[u].insert(dp[u].end(), dp[v].begin(), dp[v].end());
        
        // Clear child memory to be safe
        vector<long long>().swap(dp[v]);
    }
    
    // 2. Sort the merged breakpoints
    // This is the "DP" part: reconstructing the convex shape
    sort(dp[u].begin(), dp[u].end());
}

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

    int n, m;
    if (!(cin >> n >> m)) return 0;

    for (int i = 2; i <= n + m; i++) {
        int p;
        long long w;
        cin >> p >> w;
        adj[p].push_back({i, w});
        total_edge_sum += w;
    }

    solve(1);

    // Final Answer Calculation
    // The root function dp[1] tells us the cost for any distance X.
    // We want the minimum cost. The minimum of a convex function is where slope is 0.
    // Our slopes range from -M to +M (roughly).
    // The optimal X is where the slope becomes 0.
    // In our vector, the points represent slope transitions:
    // -M -> -M+1 ... -> -1 -> 0 -> 1 ...
    // The transition from -1 to 0 happens at the M-th point (0-indexed).
    // Actually, simpler: The min cost is F(0) + integral of slope.
    // Or standard formula: Cost = Sum_Edges - Sum_of_Breakpoints_associated_with_negative_slopes.
    
    // For the root, we have M leaves. Slope starts at -M.
    // We need to sum the first M breakpoints (which bring slope from -M to 0).
    
    long long subtraction_sum = 0;
    int k = dp[1].size() / 2; // Number of leaves M
    
    for (int i = 0; i < k; i++) {
        subtraction_sum += dp[1][i];
    }

    cout << total_edge_sum - subtraction_sum << endl;

    return 0;
}

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