Submission #1159565

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159565		Tenis0206	Fireworks (APIO16_fireworks)	C++20	100 / 100	131 ms	84880 KiB

fireworks

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int nmax = 3e5;

int n, m;
int t[nmax + 5], c[nmax + 5];

vector<int> G[nmax + 5];

struct funct
{
    int a, b;
    priority_queue<int> *h;

    funct()
    {
        a = b = 0;
        h = new priority_queue<int>;
    }

    void operator += (funct other)
    {
        a += other.a;
        b += other.b;
        if(other.h->size() > h->size())
        {
            swap(other.h, h);
        }
        while(!other.h->empty())
        {
            h->push(other.h->top());
            other.h->pop();
        }
    }

    void elim(int slope)
    {
        while(a > slope)
        {
            b += h->top();
            h->pop();
            --a;
        }
    }

    void shift(int len)
    {
        b -= len;
        int poz1 = h->top();
        h->pop();
        int poz2 = h->top();
        h->pop();
        h->push(poz1 + len);
        h->push(poz2 + len);
    }
};

funct f[nmax + 5];

void dfs(int nod)
{
    if(nod > n)
    {
        f[nod].a = 1;
        f[nod].b = -c[nod];
        f[nod].h->push(c[nod]);
        f[nod].h->push(c[nod]);
        return;
    }
    for(auto it : G[nod])
    {
        dfs(it);
        f[nod] += f[it];
    }
    f[nod].elim(1);
    f[nod].shift(c[nod]);
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=2;i<=n+m;i++)
    {
        cin>>t[i]>>c[i];
        G[t[i]].push_back(i);
    }
    dfs(1);
    f[1].elim(0);
    cout<<f[1].b<<'\n';
    return 0;
}

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