Submission #1286958

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286958		MMihalev	Tree (IOI24_tree)	C++20	0 / 100	2148 ms	1286948 KiB

tree

#include<iostream>
#include<algorithm>
#include<vector>
#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];
vector<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)
{
    for(int v:g[u])
    {
        dfs(v);
        sum[u]+=sum[v];
        for(auto [price,howmuch]:rem[v])
        {
            rem[u].push_back({price,howmuch});
        }
    }
    if(deg[u]==0)
    {
        sum[u]=l;
        ans+=l*w[u];
        return;
    }
    sort(rem[u].rbegin(),rem[u].rend());
    long long haveto=sum[u]-r;
    while(haveto>0 && rem[u].size())
    {
        auto [price,howmuch]=rem[u].back();
        if(w[u]>price)
        {
            long long need=min(haveto,howmuch);
            haveto-=need;
            ans+=price*need;
            if(howmuch==need)
            {
                rem[u].pop_back();
            }
            else
            {
                rem[u].back().second=howmuch-need;
                break;
            }
        }
        else
        {
            ans+=haveto*w[u];
            rem[u].clear();
            if(r>l)rem[u].push_back({w[u],r-l});
            break;
        }
    }
    reverse(rem[u].begin(),rem[u].end());
    while(rem[u].size() && rem[u].back().first>w[u])
    {
        rem[u].pop_back();
    }
    long long cursum=sum[u];
    for(auto [price,howmuch]:rem[u])
    {
        cursum-=howmuch;
    }
    if(cursum>l)rem[u].push_back({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: 0 / 10
• Subtask 2: 0 / 13
• Subtask 3: 0 / 18
• Subtask 4: 0 / 7
• Subtask 5: 0 / 11
• Subtask 6: 0 / 22
• Subtask 7: 0 / 19