Submission #1308209

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308209		orzorzorz	Fireworks (APIO16_fireworks)	C++20	100 / 100	342 ms	45020 KiB

fireworks

/**
 * APIO 2016 - Fireworks
 * Solution using Slope Trick and Leftist Heaps
 * 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; // Null Path Length for Leftist property
    Node *l, *r;
    Node(long long v) : val(v), dist(0), l(nullptr), r(nullptr) {}
};

// Merge two Leftist Heaps (Max Heap)
Node* merge(Node* a, Node* b) {
    if (!a) return b;
    if (!b) return a;
    
    // Max Heap property: larger value at root
    if (a->val < b->val) swap(a, b);
    
    a->r = merge(a->r, b);
    
    // Leftist property: dist of left child >= dist of right child
    if (!a->l || a->l->dist < a->r->dist) swap(a->l, a->r);
    
    a->dist = a->r ? a->r->dist + 1 : 0;
    return a;
}

// Pop root and return new root
Node* pop(Node* root) {
    if (!root) return nullptr;
    Node* res = merge(root->l, root->r);
    delete root; // Clean up memory
    return res;
}

const int MAXN = 300005;
vector<int> adj[MAXN];
long long edge_weight[MAXN];
Node* heaps[MAXN];
long long total_edge_sum = 0;

void dfs(int u) {
    // Process all children
    for (int v : adj[u]) {
        dfs(v);
        heaps[u] = merge(heaps[u], heaps[v]);
    }

    if (u != 1) { // If not root
        if (adj[u].empty()) {
            // Leaf Node Logic
            // Function is |x - w|, slopes change at w and w
            long long w = edge_weight[u];
            heaps[u] = merge(heaps[u], new Node(w));
            heaps[u] = merge(heaps[u], new Node(w));
        } else {
            // Internal Node Logic
            int deg = adj[u].size();
            
            // Pop 'deg - 1' largest breakpoints to flatten slope > 1 to 1
            while (deg > 1) {
                heaps[u] = pop(heaps[u]);
                deg--;
            }
            
            // Extract the optimal interval [L, R]
            long long R = heaps[u]->val; heaps[u] = pop(heaps[u]);
            long long L = heaps[u]->val; heaps[u] = pop(heaps[u]);
            
            // Shift by edge weight and push back
            // The cost function is extended by w
            heaps[u] = merge(heaps[u], new Node(R + edge_weight[u]));
            heaps[u] = merge(heaps[u], new Node(L + edge_weight[u]));
        }
    } else {
        // Root Logic
        int deg = adj[u].size();
        
        // We want the minimum value, which occurs when slope is 0.
        // The heap currently ends with max slope 'deg'.
        // We pop 'deg' times to remove all positive slope parts.
        while (deg > 0) {
            heaps[u] = pop(heaps[u]);
            deg--;
        }
        
        // The minimum cost is: (Sum of all weights) - (Sum of remaining breakpoints)
        // This formula derives from integrating the negative slopes.
        while (heaps[u]) {
            total_edge_sum -= heaps[u]->val;
            heaps[u] = pop(heaps[u]);
        }
    }
}

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

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

    // Input format: Line i (for i=2...N+M) contains Parent and Weight
    for (int i = 2; i <= N + M; i++) {
        int p;
        long long w;
        cin >> p >> w;
        adj[p].push_back(i);
        edge_weight[i] = w;
        total_edge_sum += w;
    }

    dfs(1);

    cout << total_edge_sum << endl;

    return 0;
}

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