Submission #1305883

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305883		orzorzorz	Fireworks (APIO16_fireworks)	C++20	100 / 100	278 ms	47196 KiB

fireworks

/**
 * APIO 2016 - Fireworks
 * Solution by Gemini
 * * Approach: Slope Trick with Leftist Heap
 * Time Complexity: O((N+M) log(N+M))
 */

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

using namespace std;

// Leftist Heap Node
struct Node {
    long long val;
    int dist; // Distance to null node (for leftist property)
    Node *l, *r;

    Node(long long v) : val(v), dist(1), l(nullptr), r(nullptr) {}
};

// Merge two leftist heaps
Node* merge(Node* a, Node* b) {
    if (!a) return b;
    if (!b) return a;
    
    // Max-Heap property: larger values on top
    if (a->val < b->val) swap(a, b);
    
    a->r = merge(a->r, b);
    
    if (!a->l || (a->r && a->l->dist < a->r->dist)) {
        swap(a->l, a->r);
    }
    
    a->dist = (a->r ? a->r->dist : 0) + 1;
    return a;
}

Node* pop(Node* root) {
    Node* l = root->l;
    Node* r = root->r;
    delete root; // Clean up memory
    return merge(l, r);
}

const int MAXN = 300005;
vector<pair<int, int>> adj[MAXN]; // Adjacency list: {child, weight}
Node* heaps[MAXN];
int N, M;

int main() {
    // Optimize I/O operations
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    if (!(cin >> N >> M)) return 0;

    // The total number of nodes is N + M
    // Input format: parents for nodes 2 to N+M
    for (int i = 2; i <= N + M; ++i) {
        int p;
        long long w;
        cin >> p >> w;
        adj[p].push_back({i, (int)w});
    }

    // Process the tree from bottom up (Post-order traversal)
    // Since node indices are topological (parents < children usually, but let's do explicit DFS)
    // Actually, explicit DFS is safer.
    
    // We can use a non-recursive approach or recursive. 
    // Given depth, recursive is fine. N+M = 300,000 might risk stack overflow on some systems,
    // but typically 256MB stack is enough. We'll use recursive DFS.
    
    // We need to calculate base cost: sum of all edge weights.
    // The "slope trick" calculates the reduction/increase relative to a baseline.
    // Specifically, f(0) = sum(all weights).
    
    long long base_cost = 0;

    // DFS lambda
    // We can't use std::function efficiently for competitive programming sometimes, 
    // but a manual recursive function is fine.
    // We'll traverse using a manual stack or just standard recursion.
    // Let's use a standard recursive function defined outside or strict ordering.
    // Since input P_i < i is NOT guaranteed, we must use DFS.
    
    auto dfs = [&](auto&& self, int u) -> void {
        // If leaf (Explosive)
        if (adj[u].empty()) {
            // Leaf cost function corresponds to slopes -1, 1 breaking at 0.
            // But we process the edge to parent at the parent's level? 
            // No, the standard slope trick pushes the edge effect at the node.
            // For a leaf, distance 0 cost is 0. 
            // Breakpoints at 0, 0 (slope changes -1 -> 0 -> 1).
            heaps[u] = new Node(0);
            heaps[u] = merge(heaps[u], new Node(0));
            return;
        }

        for (auto& edge : adj[u]) {
            int v = edge.first;
            int w = edge.second;
            base_cost += w;
            
            self(self, v);
            
            // Merge child's heap into current
            heaps[u] = merge(heaps[u], heaps[v]);
        }

        // Processing at node u (before passing to parent)
        // We have merged all children.
        // Current max slope is roughly equal to degree (number of children).
        // We need to shape the function for the edge extending upwards from u.
        // The transformation requires max slope to be 1.
        // So we pop (degree - 1) largest elements.
        
        // Note: For a leaf, we created {0, 0}. Max slope 1.
        // For internal node u, we merged children.
        // If u has k children, each child ends with slope 1 (after their processing).
        // So sum ends with slope k.
        // We want to reduce slope to 1. So pop k-1 elements.
        
        int k = adj[u].size();
        for (int i = 0; i < k - 1; ++i) {
            heaps[u] = pop(heaps[u]);
        }

        // Now we apply the edge weight shift.
        // The transformation: f_new(x) = min_y (f_old(y) + |x - y - w|)
        // This shifts the "slope 0" and "slope 1" transition points by w.
        // Top of heap is R (slope 1 transition).
        // Next is L (slope 0 transition).
        
        long long R = heaps[u]->val;
        heaps[u] = pop(heaps[u]);
        
        long long L = heaps[u]->val;
        heaps[u] = pop(heaps[u]);
        
        // Push shifted values
        // Note: We access the parent edge weight in the caller or here?
        // The problem is we need the weight of the edge ABOVE u.
        // But the current logic inside `for` loop handled `base_cost` for edge u->v.
        // The edge above u is handled when `dfs(parent)` calls `dfs(u)`.
        // Wait, we need to apply the edge weight of u->parent NOW.
        // But we don't have it easily. 
        // We should actually handle the "shift" logic using the edge leading TO u.
        // The problem description gives edges from P to i.
        // So we need to look up weight of edge parent[u] -> u.
        // Actually, simpler: pass weight in DFS.
    };

    // Redefine DFS to take edge weight to parent
    auto dfs_refined = [&](auto&& self, int u, int w_to_parent) -> void {
        if (adj[u].empty()) {
            // Leaf
            // Initial breakpoints 0, 0.
            heaps[u] = new Node(0);
            heaps[u] = merge(heaps[u], new Node(0));
        } else {
            for (auto& edge : adj[u]) {
                int v = edge.first;
                int w = edge.second;
                base_cost += w;
                self(self, v, w);
                heaps[u] = merge(heaps[u], heaps[v]);
            }
            
            // Pop degree-1 elements
            int k = adj[u].size();
            for (int i = 0; i < k - 1; ++i) {
                heaps[u] = pop(heaps[u]);
            }
        }
        
        // Apply edge weight w_to_parent
        // If u is root (1), w_to_parent is 0 or irrelevant (we don't shift at root).
        if (u != 1) {
            long long R = heaps[u]->val;
            heaps[u] = pop(heaps[u]);
            
            long long L = heaps[u]->val;
            heaps[u] = pop(heaps[u]);
            
            heaps[u] = merge(heaps[u], new Node(R + w_to_parent));
            heaps[u] = merge(heaps[u], new Node(L + w_to_parent));
        }
    };

    dfs_refined(dfs_refined, 1, 0);

    // Final Calculation at Root
    // The heap contains change points.
    // Slope starts at -M (number of leaves).
    // F(0) = base_cost.
    // We integrate until slope becomes 0.
    // The slope becomes 0 after M increments.
    // Since heap is Max-Heap, it stores the LARGEST change points.
    // The points where slope is negative are the smallest ones (deep in heap or not popped).
    // The range of slopes is [-M, M]. Total 2M points.
    // We want the value at the point where slope becomes 0.
    // That is the M-th smallest point.
    // Since we have a Max-Heap of size 2M (roughly), the M-th smallest is the (Size - M + 1)-th largest.
    // Or more simply:
    // We just pop elements. Each pop corresponds to a slope segment at the far right.
    // Slope at far right (after last point) is M.
    // Pop 1 -> slope M-1.
    // ...
    // Pop M -> slope 0.
    // So we just need to integrate backwards from infinity?
    // No, standard way:
    // Sort all points. Calculate from 0.
    
    vector<long long> points;
    while (heaps[1]) {
        points.push_back(heaps[1]->val);
        heaps[1] = pop(heaps[1]);
    }
    sort(points.begin(), points.end());

    // Logic:
    // f(x) has slope -M at x=0.
    // f(0) = base_cost.
    // Points p_0, p_1, ... 
    // Cost at p_0 (first change point):
    // f(p_0) = f(0) + slope * (p_0 - 0) = base_cost + (-M) * p_0.
    // New slope = -M + 1.
    // And so on.
    // We stop when slope becomes 0.
    
    long long current_cost = base_cost;
    long long current_slope = -M;
    long long prev_x = 0;

    for (long long x : points) {
        current_cost += current_slope * (x - prev_x);
        current_slope++;
        prev_x = x;
        if (current_slope == 0) break;
    }

    cout << current_cost << endl;

    return 0;
}

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