Submission #1286967

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286967		MMihalev	Tree (IOI24_tree)	C++20	23 / 100	2097 ms	47036 KiB

tree

#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#include "tree.h"
using namespace std;
const int MAX_N=2e5+5;
long long w[MAX_N];
vector<int>g[MAX_N];
int deg[MAX_N];
multiset<pair<long long,long long>>rem[MAX_N];
int n;
long long l,r;
long long ans;
long long sum[MAX_N];

void dfs(int u)
{
    int mxsz=0;
    int which=-1;
    for(int v:g[u])
    {
        dfs(v);
        sum[u]+=sum[v];
        if(rem[v].size()>mxsz)
        {
            mxsz=rem[v].size();
            which=v;
        }
    }
    if(which!=-1)
    {
        swap(rem[which],rem[u]);
        multiset<pair<long long,long long>>().swap(rem[which]);
    }
    for(int v:g[u])
    {
        if(v!=which)
        {
            for(auto [price,howmuch]:rem[v])
            {
                rem[u].insert({price,howmuch});
            }
            multiset<pair<long long,long long>>().swap(rem[v]);
        }
    }

    if(deg[u]==0)
    {
        sum[u]=l;
        ans+=l*w[u];
        return;
    }
    long long haveto=sum[u]-r;
    while(haveto>0 && rem[u].size())
    {
        auto [price,howmuch]=(*(rem[u].begin()));
        if(w[u]>price)
        {
            long long need=min(haveto,howmuch);
            rem[u].erase(rem[u].find({price,howmuch}));
            haveto-=need;
            sum[u]-=need;
            ans+=price*need;
            if(howmuch==need)
            {
                ;
            }
            else
            {
                rem[u].insert({price,howmuch-need});
                break;
            }
        }
        else
        {
            ans+=haveto*w[u];
            sum[u]-=haveto;
            rem[u].clear();
            haveto=0;
            break;
        }
    }
    if(haveto>0)
    {
        ans+=haveto*w[u];
        sum[u]-=haveto;
    }
    while(rem[u].size() && (*(rem[u].rbegin())).first>=w[u])
    {
        rem[u].erase(rem[u].find((*(rem[u].rbegin()))));
    }
    long long cursum=sum[u];
    for(auto [price,howmuch]:rem[u])
    {
        cursum-=howmuch;
    }
    if(cursum>l)rem[u].insert({w[u],cursum-l});
}
void init(std::vector<int> P, std::vector<int> W)
{
    n=P.size();
    w[0]=W[0];
    for(int i=1;i<n;i++)
    {
        w[i]=W[i];
        deg[P[i]]++;
        g[P[i]].push_back(i);
    }
}

long long query(int L, int R)
{
    l=L;
    r=R;
    ans=0;
    for(int i=0;i<n;i++){rem[i].clear();sum[i]=0;}
    dfs(0);
    return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 0 / 18
• Subtask 4: 0 / 7
• Subtask 5: 0 / 11
• Subtask 6: 0 / 22
• Subtask 7: 0 / 19