Submission #679151

#	Time	Username	Problem	Language	Result	Execution time	Memory
679151		socpite	Fireworks (APIO16_fireworks)	C++17	100 / 100	236 ms	59184 KiB

fireworks

#include<bits/stdc++.h>
using namespace std;

#define f first
#define s second

typedef long long ll;

const int maxn = 3e5+5;
const int mod = 998244353;
const ll inf = 1e18;

int n, m;

ll W[maxn];

int hh[maxn], sz[maxn];

priority_queue<ll> pq[maxn];

vector<int> graph[maxn];

pair<ll, ll> func[maxn];

void ph(int x){
    func[x].s+=pq[x].top();
    pq[x].pop();
    func[x].f--;
}

void add(int x, ll val){
    func[x].s -= val;
    pq[x].push(val);
    func[x].f++;
}

void Union(int x, int d){
    func[x].f += func[d].f;
    func[x].s += func[d].s;
    while(!pq[d].empty()){
        pq[x].push(pq[d].top());
        pq[d].pop();
    }
}

void dfs(int x){
    sz[x]++;
    if(x > n){
        func[x] = {1, -W[x]};
        hh[x]=x;
        pq[x].push(W[x]);
        pq[x].push(W[x]);
    }
    else{
        int bc = 0;
        for(auto v: graph[x]){
            dfs(v);
            sz[x]+=sz[v];
            if(sz[bc] < sz[v])bc = v;
        }
        int id = hh[bc];
        hh[x] = id;
        for(auto v: graph[x]){
            if(v == bc)continue;
            Union(id, hh[v]);
        }
        func[id].s+=W[x];
        while(func[id].f > 1)ph(id);
        ll p1 = pq[id].top();
        ph(id);
        ll p2 = pq[id].top();
        ph(id);
        add(id, p1+W[x]);
        add(id, p2+W[x]);
    }
    //cout << x << " " << func[hh[x]].f << " " << func[hh[x]].s << "\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for(int i = 2; i <= n+m; i++){
        int x;
        cin >> x >> W[i];
        graph[x].push_back(i);
    }
    dfs(1);
    ph(hh[1]);
    cout << func[hh[1]].s;
}

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