제출 #683947

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
683947		PoonYaPat	Fireworks (APIO16_fireworks)	C++14	7 / 100	5 ms	7372 KiB

fireworks

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

int n,m;
struct A {
    int L,R;
    ll y_min;
};
vector<pii> adj[300001];

A dfs(int x, int par) {
    priority_queue<int, vector<int>, greater<int>> rsq;
    priority_queue<int> lsq;
    ll Y=0;
    bool ex=true;

    for (auto s : adj[x]) {
        if (s.first==par) continue;
        ex=false;
        A node=dfs(s.first,x);
        Y+=node.y_min;

        if (lsq.size()>0) {
            if (node.L+s.second>rsq.top()) Y+=node.L+s.second-rsq.top();
            if (node.R+s.second<lsq.top()) Y+=lsq.top()-node.R-s.second;
        }

        lsq.push(node.L+s.second); lsq.push(node.R+s.second);
        rsq.push(lsq.top()); lsq.pop();

        while (lsq.top()>rsq.top()) {
            int a=rsq.top(),b=lsq.top();
            lsq.pop(); rsq.pop();
            lsq.push(a); rsq.push(b);
        }

    }

    if (ex) return {0,0,0};
    else return {lsq.top(),rsq.top(),Y};
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m;
    for (int i=2; i<=n+m; ++i) {
        int a,b; cin>>a>>b;
        adj[i].push_back(pii(a,b));
        adj[a].push_back(pii(i,b));
    }
    cout<<dfs(1,0).y_min;
}

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