Submission #1308248

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

fireworks

/**
 * APIO 2016 - Fireworks (煙火表演)
 * 解法：Slope Trick + Small-to-Large Merging (啟發式合併)
 * 時間複雜度：O((N+M) log^2 (N+M))
 */

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

using namespace std;

const int MAXN = 300005;

// 鄰接表：存儲子節點
vector<int> adj[MAXN];
// 邊權：edge_weight[i] 表示節點 i 與其父節點之間的邊權
long long edge_weight[MAXN];
// 每個節點維護一個 Max Heap (用 priority_queue 實作)
priority_queue<long long>* pq[MAXN];
// 記錄所有邊權的總和
long long total_edge_sum = 0;

void dfs(int u) {
    // 初始化當前節點的 heap
    pq[u] = new priority_queue<long long>();

    // 遍歷所有子節點
    for (int v : adj[u]) {
        dfs(v);
        
        // --- Small-to-Large Merging (啟發式合併) ---
        // 確保 u 的 heap 總是比較大的那個，以減少搬移次數
        if (pq[u]->size() < pq[v]->size()) {
            swap(pq[u], pq[v]);
        }
        
        // 將 v (較小的 heap) 中的元素全部轉移到 u (較大的 heap)
        while (!pq[v]->empty()) {
            pq[u]->push(pq[v]->top());
            pq[v]->pop();
        }
        // 釋放 v 的記憶體
        delete pq[v];
    }

    // 處理當前節點的函數變化
    // 1. 如果是葉子節點 (除了根節點外)
    if (adj[u].empty() && u != 1) {
        long long w = edge_weight[u];
        // 葉子的函數是 |x - w|，轉折點為 w, w
        pq[u]->push(w);
        pq[u]->push(w);
        pq[u]->pop();
    } 
    // 2. 如果是內部節點 (非根)
    else if (u != 1) {
        long long w = edge_weight[u];
        int deg = adj[u].size();

        // 彈出 deg - 1 個最大值，將斜率修正為 1
        // 因為每條邊只能貢獻 1 的斜率變化
        while (deg > 1) {
            pq[u]->pop();
            deg--;
        }

        // 取出斜率為 0 的區間端點 [L, R]
        long long R = pq[u]->top(); pq[u]->pop();
        long long L = pq[u]->top(); pq[u]->pop();

        // 加上邊權 w 並放回堆中 (平移函數)
        pq[u]->push(R + w);
        pq[u]->push(L + w);
    } 
    // 3. 如果是根節點
    else {
        int deg = adj[u].size();
        
        // 根節點不需要考慮父邊，只需找到最小值
        // 最小值在斜率為 0 處取得，將所有斜率 > 0 的部分彈出
        // 堆中目前有 deg 個斜率 > 0 的轉折點
        while (deg > 0) {
            pq[u]->pop();
            deg--;
        }
        
        // 計算答案
        // 最小代價 = 總邊權 - 剩餘轉折點之和
        while (!pq[u]->empty()) {
            total_edge_sum -= pq[u]->top();
            pq[u]->pop();
        }
    }
}

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

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

    // 讀取輸入
    // 題目輸入從第 2 行開始，描述節點 2 到 N+M 的父節點 p 和邊權 w
    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: 0 / 7
• Subtask 2: 0 / 19
• Subtask 3: 0 / 29
• Subtask 4: 0 / 45